Yes, definitely make sure AT&T has visual voicemail set up for you. If you've installed AT&T Messages (which does visual voicemail but also forces you to see text msg notifications), you need to call AT&T and ask them to roll you back to regular visual voicemail (reset it, effectively).
The AT&T Visual Voicemail app (the one I provide the link for - to XDA) works great. I've never felt the need for Google Voice, since I had visual voicemail on my iPhone, and it worked great as a native capability. I didn't really want to go with Voice just to get visual voicemail, so I am happy with my choice right now. Although I heard Google Voice Light lets you do just the visual voicemail part, which is nice.