Jonathan,
Lr always stores changes to photos in its internal database. This includes both parametric image adjustments (the changes to the image) and changes to metadata, e.g. IPTC, keywords, ratings, labels. In addition Lr enables and tracks various collection membership, sort parameters, view management things like that. Basically, everything Lr can do is stored in that database.
A subset of those parameters (in Adobe's XMP data format) also can, optionally, be stored directly with the original image files. The implementation of this depends on the filetype of the original image file. Proprietary format camera raw files are treated as read-only, and the XMP data is stored in a per-image auxiliary file, termed a sidecar file. Standard file types, JPG, DNG, TIF, and PSD, have provisions for storing the XMP data internally in a standard format.
Principally this is important, because this optional storage method provides a safety net of associating important image data with the individual images. This will potentially permit recovery from a fubar situation where the Lr catalog database is corrupt and unrecoverable. In the future, it may also enhance interchangability of adjustment data between programs, but currently is only standardized amongst Adobe applications, principally Lr and the ACR component of Photoshop.
This practice is a perennial topic of debate among Lr enthusiasts. My general personal preference is to save XMP data, but I'm not fanatical about it. The primary points of contention are the complexity of managing extra files and a frequently noticeable performance hit due to the extra read/write disk activity involved in the process, particularly with large catalogs. (Large tends to be a fluid concept based on your particular system's CPU and I/O capabilities)