However, you are right that 'lossy' is usually used to describe its intended use rather than its actual formal limit. For example, you can (probably!) non-lossily encode an image as a jpeg, but it won't be as good a compression ratio as you would get from a format which was specifically designed for use with lossless compression. It might even cause the file to get bigger.
Various techniques are used to accomplish this. One side of the scale is to simply degrade the quality of the original. The other is to use visual/acoustic changes humans have difficulty in recognizing. For instance, the human hear has a minimum distance between frequency and loudness of two tones. The softer tone is dropped in MP3 depending on "compression" level; thus, from a source fidelity standpoint, the quality is "lossy" since the encoded form no longer has the original's content. From a human ear quality standpoint, the quality is barely noticeable to most people.
A lossy codec would take advantage of limits in human perception and encode LightBlue-MediumBlue-DarkBlue as 2LightBlue-DarkBlue. On a large enough image, you wouldn't notice the difference.
The correct mathematical term for "lossy" is "non-surjective": at a given encoding setting, not all inputs can be represented.