Q:

Is there a general formula for image size vs. print size?

What size images do I need for common print sizes, such as wallet size, 8x10, and 16x20?  Is there a general formula?
How could that size change if, for example, a 16x20 was printed on canvas rather than photopaper?

A:

There are some general rules you can use to determine the "maximum" (I use that term loosely) print size. Keep in mind that the quality of a print is often more dependent on what is being printed than its size in megapixels, and even if your image size is not dense enough to mathematically fit onto a certain page size, you can still blow most images up pretty large without significant or noticable loss in quality.
Anyway, as a general formula:

[width in pixels] / [print pixels per
  inch] = [print width in inches]
  [height in pixels] / [print pixels per
  inch] = [print height in inches]

Screen/camera pixels do not directly translate to print pixels (PPI, pixels per inch), so you need to translate your image pixel size into a print size by dividing your screen pixel sizes by the PPI of your print. Assuming you have an 8mp camera, your image sizes are likely to be around 3200 x 2400 or so. If you print at the native "photo quality" PPI of an Epson printer of 300ppi, you would end up with the following:

3200 pixels / 300 ppi = 10.7"
  2400 pixels / 300 ppi = 8"

That boils down to an 8.5 x 11 print at full resolution without any loss of quality or resolution in the translation between screen and print. However, this is not a general rule for print quality...it is simply a rule for ascertaining the lossless print size for a given image size. You could still blow up your 8mp photo and print it at 11x16, or 13x19, and still have a good print. 
You can use this formula in reverse as well, to determine the screen pixel size your image would need to be to be for a particular paper size:

[print width in inches] * [ppi] =
  [width in pixels]
  [print height in
  inches] * [ppi] = [height in pixels]

Using this, you could determine what size image you would need for a 2x3 inch print:

2" * 300 ppi = 600 pixels
  3" * 300 ppi = 900 pixels

There are other things you can do with your image to improve its quality when printed. Sharpening an image before printing, assuming you do so with the proper care, can improve the quality of your printed copies. It is also possible to use image editing software, such as Photoshop or QImage, to digitally blow up your image to a higher resolution, perform some post process sharpening, and print at even larger sizes.
Beyond this relatively simple explanation, the discussion of how to translate a photo image to its printed paper size is a relatively complex topic. It is possible to print at a variety of PPI, from as low as 100 to as high as 480 or higher. The PPI you choose to print at, the size of your image, and the quality of the algorithms you may have used to scale your image up or down, the texture, brightness, thickness, and color of your paper, and the kind of printer all determine how good a photo looks when printed.

A:

I'm going to sort of disagree with all the other answers that talk about DPI or PPI rules of thumb, and suggest two different 'rules' (based on PPD, from another answer of mine)
Rule 1 — The 'Retina' rule
(aka the Pixels-Per-Degree (PPD) / 'better than your eye can see' rule)
This comes pretty much straight from Apple's Retina display designs, the idea being that our eye can resolve some number of pixels per degree, so the resolution of the image/print must be taken in consideration with the intended viewing distance.
In short, Apple suggest a minimum 53 PPD, others suggest up to 100 (especially if your vision is better than 20/20).
You can easily calculate one of PPD, PPI and viewing distance (d) based on the other two:
PPD = d * PPI * 2 * tan(pi/360)     ≈ d * PPI * 0.01745
PPI = PPD / (d * 2 * tan(pi/360))   ≈ PPD / (d * 0.01745)
  d = PPD / (PPI * 2 * tan(pi/360)) ≈ PPD / (PPI * 0.01745)

You may have a constrained PPI (if already printed), a constrained viewing distance (based on the intended usage or space limitations) and/or a PPD you're trying to achieve (e.g. 75 to pick an arbitrary value between 53 and 100). Note that larger viewing distances than the d calculated are OK, it's just going closer that will allow viewers to 'see the pixels'.
If you're asking this question well ahead of time, you can choose your PPD (and I suggest you pick at least 53, and anything beyond about 100 is wasted effort), and based on your viewing distance determine the required PPI. This either tells you the maximum print size (if your camera resolution is the limiting factor) and/or the required image resolution from your camera/photographer.
Examples
Anything hand-held may be viewed as close as about 15cm (~6"), though more likely about 25cm (10"), so for 75 PPD you'd want 430 PPI (10"), but even at 300 PPI you're getting ~52 PPD at 25cm (10"). If it's really for close-up viewing (or magnified viewing) you're going to want to go well beyond 300 PPI (and you'll have to work out the effects of any magnification to achieve a suitable PPD).
Anything framed or wall-mounted is more likely to be viewed at 50cm (20") to 2m (80"), so for 75 PPD you'd want about 215 PPI to 55 PPI respectively.
A billboard could be designed for viewing from 10m (33') away, so 75 PPD would require a mere 11 PPI for the print (go and look at a billboard or really large poster advertisement close up some time, the photo's 'pixels' are often clearly visible and several mm wide).
Rule 2 — The '45' rule
(aka the 'Comfortable viewing distance' / 'yes, your camera is good enough' rule)
This is a simplification of the first rule, which applies to any image that you will only view in its entirety. That is, you're not getting in closer to see detail (like you might in a big group photo, a huge panorama, a magazine product photo, etc). This can be anything from a framed photo up to an enormous billboard, and wall/gallery-hung prints in between. For most people, I think this would apply to most of their images.
The basic idea is that you are going to view the image as a whole, so the bigger it gets the longer the viewing distance. I'm going to define the 'Comfortable Viewing Distance' as "the distance at which the image fits within a 45º field-of-view", which happens to be about the same as the field of view of a 45mm lens on a 35mm/full-frame camera (and is vaguely similar in some ways to the FoV of your eye).
It's an arbitrary number, and you can adjust accordingly, though if you have a specific context or space in mind, you're probably using the first rule anyway (after all this is just a simplified version for a specific use case).
Since the required PPI is linearly dependent on the viewing distance, and the viewing distance is linearly dependent on the size of the image, and the size of the image is dependent on the resolution and PPI... the PPI ends up cancelling out and you can just work out a required resolution given your desired PPD and FoV angle (I've picked 45).
For an angle of 45º, this ends up being simply:
pixel dimensions = desired PPD x 45    (replace 45 with desired viewing angle)

Again, useful PPD ranges are 53–100, and useful viewing angles might be 20–60 (even 60 you're not really seeing the whole image anymore, so go back to rule 1).
So for the our arbitrary 75 PPD requirement and 45º viewing angle, we'd want an image that's about 3400 pixels wide (2250x3375 ~ 8 megapixels)—always.
The image resolution required is static, if the viewing angle is fixed.
For Apple's lowest Retina PPD of 53, this could be as low as ~1600x2400 (~4MP) and for the higher 100 PPD requirement, you'd need ~3000x4500 (~14MP). Even that isn't a very high resolution in today's cameras (my old 450D does 12MP).
And that's why some argue that some specific (and often quite low) resolution is plenty for just about any purpose (meaning purposes where the image is viewed as a whole, from whatever distance makes sense to do so for the size of the print).
I have a poster-sized print made from a 6MP photo (from my old 450D, which for some reason I was shooting at half-resolution JPEGs) but you'd never notice is printed at "only" ~75 DPI, because its mounted on the wall and there's no reason to get up close and personal with it (other than to pixel peep). It's mostly viewed at 1–2 metres (3–7') so works out to about 53–107 PPD.
In defense of minimum DPI/PPI rules
Ok so as much as I dislike hard DPI/PPI rules, the other side of the coin which is certainly still valid is that especially high print resolutions (e.g. in glossy magazines/brochures) add a sense of quality/precision that goes beyond simply not seeing pixels at the expected viewing distance. The viewer may not be looking closer at individual photos to see their detail, but instead may be looking closer at the magazine/brochure itself (not necessarily intentionally) and become aware of the print quality (or lack thereof).
Also if your viewers are pixel peepers.

A:

The information above is quite good, so I won't try to compete, but here is a nice infographic:

The boxes are the number of megapixels for a print of the size in inches according to the scales on the axes. This is at 300ppi, which is a standard for the print resolution of many images.
This great graphic comes from an article at D215.

