Are there any algorithms or tools that can increase the resolution of an image - besides just a simple zoom that makes each individual pixel in the image a little larger?
I realize that such an algorithm would have to invent pixels that don't really exist in the original image, but I figured there might be some algorithm that could intelligently figure out what pixels to add to the image to increase its resolution.
Enlarging images is risky. Beyond a certain point, enlarging images is a fool's errand; you can't magically synthesize an infinite number of new pixels out of thin air. And interpolated pixels are never as good as real pixels. That's why it's more than a little artificial to upsize the 512x512 Lena image by 500%. It'd be smarter to find a higher resolution scan or picture of whatever you need* than it would be to upsize it in software.
Most decent image editors have smoothing/interpolating filters to do this kind of resizing/resampling, e.g. IrfanView which gives you several options for interpolation filters. See Lanczos resampling. ImageMagick's convert program allows you to do this also, after specifying a filter
If you need to do this algorithmically, check out the Image Scaling link suggested by Draemon. What platform will you be doing these interpolations on? Most graphics libraries will have a variety of approaches implemented, allowing you to balance speed against quality.
If you just need to resize some images, I recommend GIMP. It can resize images in a variety of ways, at least one of which should produce excellent results in any situation.
As others are pointing out, you can't expect a scaling method to invent information that isn't in the original image. So you can't expect it to be like the moments in CSI where they "zoom and enhance" to see the number on a license plate that was hopelessly blurred in the original image.
For actual algorithms check out image interpolation.
The simple answer to your question is, "Yes there are algorithms, but none of them are very good." As you mentioned in the question, the limiting factor is the need to invent pixels in order to increase resolution beyond a small amount. (That's why you can't really read a license plate number from the reflection in someone's glasses off of a photo taken from a CCTV security camera, like they do in CSI: Miami.)
If all you want to do is create a larger image (for a wall hanging, or such like) then you can use a plugin for Photoshop that will smooth transitions between pixels using existing information. It can't create new pixels, but it can get rid of that boxy, pixelated look.
Addendum to the previous answers: Please note that the answer to your question depends heavily on what exactly you mean by resolution - of the display device, of the capture device, or of the viewing device (i.e., the human eye.) I assume you're talking about raster images (the problem wouldn't exist for vector images.)
You must accept that a picture taken at a higher resolution will contain more image information (i.e. details) than a picture of the same scene taken at a lower resolution. There is no way to add this information out of thin air. Scaling algorithms synthesize some information based on the assumption of continuity between the discrete raster image elements. That "new" information is not actually new but derived from the pre-existing picture information, hence it cannot be considered to have a 100% probability of matching the original scene. Better algorithms might yield better probabilities, but their results will always have a match probability of less than 1.
You can try vectorizing the image with tools like autotrace or potrace and use it in whatever resolution you like. But it is computationally very costly so you end up with an image with few colors/features and even fewer if you need to work on its whole quickly.
There is a SIGGRAPH 2007 paper on content aware image scaling. You can see a demo on youtube. It depends on application but most probably this will be an overkill.