Fundamentally, you are absolutely correct. You can only have so much information in an image. When you take a picture, that is all you have. You can’t enhance it to create more information than what's in the existing image.
It really annoys me when a police drama on TV has a scene where somebody enlarges an image and zooms in on a tiny area... to find that area is now all of a sudden enhanced and crystal clear.
In real life, it just doesn’t work that way. Still, there are some things that can be done. Let me talk about that for a minute.
Become a Patron of Ask Leo! and go ad-free!
Beauty is in the eye of the algorithm
Human vision is an interesting thing, and most of the enhancements we discuss from time to time are often just techniques that play into how we perceive what we see.
That technique could be as simple as a resizing algorithm, which increases the size of a standard definition video to high definition, making it look smooth and seamless rather than blocky.
It could be a color adjustment algorithm, which analyzes color saturation and adjusts for things like washed-out colors in old photos.
It could be other trickery that makes a photo look more pleasing in some way.
No information is added. When you change a digital image, you remove some information, but that’s not the point. Beauty truly is in the eye of the beholder, and these kinds of changes focus on an image's appearance to the human eye.
Dust removal, red-eye correction, and other tools
There are some specific changes that are more easily understood. Dust removal is a great example. The algorithm attempts to identify specs in the photograph and removes anything that looks like a spec by replacing that area with the surrounding color instead.
It isn’t perfect. For instance, anything in the picture that isn’t a spec, but happens to be the same size and color as a spec, may be replaced accidentally.
Red-eye correction is another example. It works, but not always perfectly.
The commonality is as you say: "If it’s not in the picture to begin with, it can’t be added." What these apps do is process what is already there and make it more visually appealing to the human eye.
While it’s generally true that you can’t get more out of a single image than was there when captured, there are tricks that can be done to enhance photos when multiple near-identical source images are available (e.g. sequential frames of a video, multiple photos taken of the same subject one after the other).
More info: https://en.wikipedia.org/wiki/Superresolution
Some examples: http://www.photoacute.com/studio/examples/mac_hdd/index.html