Location Services (including automatic time zone selection, Maps, and "Find My Mac") relies on a database of Wi-Fi access points with known locations. You don't have to be connected to a wireless network, but Wi-Fi must be turned on and within range of one of those access points. Otherwise the machine won't be located at all, or the location will be wrong. Sometimes the location will be wrong because the database contains inaccurate data. That would happen, for example, if you moved from one place to another and took your Wi-Fi router with you. The router is still listed in the database, but the location is wrong.
According to reports, if you connect to a Wi-Fi network with an iPhone, the location of the network will be sent to Apple and added to the database after a delay. An iPhone, unlike other Apple devices, has built-in GPS satellite navigation, and so can locate itself independently of Wi-Fi. The phone would have to be set to share diagnostic and usage information with Apple.