As with other location-based services from Google, it relies on IP address as well as Google Gears. When this Labs feature is enabled, it adds a new setting to the Signature settings (look under General settings):
Once this is done, whenever a new email is composed, a line is appended to the signature with the location.
Seems like Google’s going overboard with location-in-everything (including offerings like Google Latitude). Weren’t web-based email services supposed to offer location privacy (since originating IP in mail headers was restricted to the IP address of the email provider)?