There's multiple levels you can take this but, admittedly, you give up some pretty nice services if you completely eliminate Google. Lowering what they track while still having access to some nice features is the route I took.
One option would be to create a new Google account that is just used to access the PlayStore. In that account I went to the Accounts & Privacy page and turned off all things related to tracking me. If you only want to use free apps you don't have to give them your credit card. You can also use Amazon's store for apps safely if that makes you feel better than using the Play Store but the selection is smaller. You can use alternative map programs (HERE, Co-Pilot, etc) and browsers (Firefox, Opera, etc) and don't sign into YouTube or use Gmail or anything else and they'll only get limited information about an account that doesn't really have any connection to the real you.
If you want to really shut them out completely you can root your device and install Cyanogenmod and block all data going to their servers. With Cyanogen, you can deny all Google apps, or any app for that matter, from having access to GPS, WiFi, Bluetooth, SMS, MMS, email, audio, your call log, your contacts, and virtually anything else on your phone. You can also delete or disable anything on your phone that says Google although you will likely have some unexpected behavior from your phone if you go that route, especially if you disable Google Play Services. Just search for, "use Android without Google" and you'll find plenty of ways to get around them.