You may get more answers if you post in the photoshop section - but a mod will move this if need be.
In PS. Go Image -> Image Size.
Change the DPI to 300. You'll notice at the top of that dialog box there will be two different megapixel sizes. The one in brackets is the size of your file before you changed your dpi. The one outside brackets is your new size.
Change the height and width of your file until the two file sizes are about the same. Or the new file size is just under the size of the old one. This is probably your optimal size that you can print at without loosing quality due to more pixels being added.
Then save as a jpeg. Ring the lab ahead of time and ask if their machines can read Tiff... if they can, save it as a tiff. That way you won't lose any detail.
I have printed images that were 5 times their original file size and they still look fine from a little bit further away than 'optimal viewing' distance, but closer you start to see the difference.
Sizes are usually done in inches, coz that's the way that photo paper is still measured. So you can do 5x7, 6x8, 8x10, 8x12 and heaps of other sizes.
Cost depends where you get it done of course. Kmart is one of the more expensive places for me, up here in Cairns. It costs about $11 to get an 8x12 there, from memory. But I found a really great semi-professional camera lab that'll do an 8x12 for $4. So it pays to shop around.
You then just take your file in on a CD and put it in one of those tricky machines and it prints out for you in a few minutes. yippee! It's magic!
Your first few prints will be printed wrongly, I can tell you that. Because their printers will be callibrated differently to your monitor. So just do a couple of small prints first off and then come back home and recalibrate your monitor to suit their machine. It's a pain in the ass but worth it, if you're going to print a bunch of stuff at the one place.