Caching with an experienced cacher is definitely the #1 way to build up your senses, if you have the connections. In addition to that and the other suggestions already given, another thing that has helped me a lot is to do some research online.
Check out YouTube, FlickR, geocaching stores, and the threads here on Groundspeak (I especially recommend the "Cool cache containers" thread). Soak up everything about geocaching you can find online, it will teach you a lot about how caches have been hidden and the most popular tricks of the trade. It can help you to recognize clues that you see out in the field.
Good luck!