depends on wear... when i wore boots a lot once every 1-2 years was necessary... now it's pretty rare. As for where to do it, I don't know where you live, but pretty much everywhere seems the same to me whether it's a boot shop, "shoe hospital", etc.
If you are up north, try Abraham's Shoe repair, 11005 N. Burnet Rd. It is across from IBM. Small place, good guy, and have done excellent work at a good price for me.
I usually take mine to Tio's Shoe Service at 7329 Burnet Rd. Good work, good price. If you wear them regularly, it could definitely be necessary once per year.
And remember, you can get them "half-soled" if you've only worn out the leather toward the front of your foot. The heels shouldn't wear out as quickly, so you don't need to get the full sole replaced every time.
I strike my heels pretty hard when i walk, so they go kinda fast, though it is the front part that has worn down on these. I wear them every day and walk a mile to and from work.