I definitely prefer Gowalla, but Foursquare has most of the buzz. I still use BrightKite and threw Whrrl into the mix. And Yelp does checkins, and Loopt is still kicking, and there's Google Latitude supposedly getting new features soon. I'm in the beta for Burbn, which is a mobile web app, and there's Rally app and MyTown and ... the list goes on and on!
I use Check.in! It works on Gowalla, Foursquare, BrightKite and Whrrl. It's built by BrightKite. And the Gowalla support is entirely a hack and I suspect could be cut off at any time. They want to add more services, but it requires more support or an API from those other services.