It really depends how deep you want to go.
I'd suggest consider it prerequisite that any service be an open 'BYOD' SIP-based serivce. SIP is the VoIP protocol most commonly used, and BYOD means Bring Your Own Device. Many SIP providers (ie Vonage) lock the service so you can't get the credentials (login/password), the service can only be used with the ATA (analog telephony adapter) they send you. That makes it useless if you want to ever use something else or a computer. BYOD generally means that you can get the config info if you want, and then plug it into something else.
As for providers, consider what you want. If you want something skype-like, gizmo is a great system. You can buy phone numbers (DIDs) or outgoing minutes for a reasonable fee.
If you want something more Vonage like, try broadvoice.com or viatalk.com. Both support BYOD. They sell you a 'line' for a monthly fee, often with many nifty features thrown in.
From there you must decide what exactly you want to do on your end. The simplest is a softphone like gnomemeeting, ekiga, etc. This however requires your computer to be on and you to use a headset to talk on the phone, which you may not want. There are many SIP-based IP phones you can buy- check out
www.voipsupply.com . In particular look at SNOM and AASTRA, both are excellent quality. Grandstream is also good if you're on a budget but their products are cheaper. However GS phones are good to learn on, myself and many other VoIP geeks cut our teeth on Grandstream BT100's back when it was the only IP phone that didn't cost $300.
You might also consider an ATA, that's basically a VoIP to POTS adapter, you plug your normal phone into it. That's the same gadget that Vonage sends you more or less.
If you want a simple solution, most providers will happily provide you with an ATA, and some (viatalk does, i think broadvoice does also) will then give you the passwords for your ATA so you can tweak it if you want. Other providers (vonage) won't give you anything.
Lastly if you want to go all the way, check out
www.asterisk.org . Asterisk is an open source VoIP software PBX that runs on Linux. it is VERY flexible, and can do almost anything.
You might also check out the voip wiki at
www.voip-info.org
hope that helps and good luck!