Wireless passwords are indeed stored on the hard drive, in something known as a "connection profile." Connection profiles, essentially, have everything the system requires to connect to every network. However, they also contain a field to identify which device the profile belongs to:
When the system tries to establish a connection using the profile it has for that WiFi network, it notices that the device IDs don't match, and therefore the profile is skipped. As no valid profile is discovered, the system assumes that the WiFi network is new and hasn't been used before. Therefore, none of the settings for the network exist, and you have to re-enter your password.
If you'd rather not re-create a new wireless profile, you can always change the device using the Connection Editor (
Edit Connections under the Wi-Fi icon), which will then allow that profile to be used with the new device. From here, you can also set other parameters for your network, as well as extract the wireless password in plaintext if need be.
If you're more adventurous and want to (ab)use the command line, connection profiles are all stored in
/etc/NetworkManager/system-connections, which contains (roughly) the same information as the GUI does:
id=[Human-Friendly Connection Name]
seen-bssids=[List of known BSSIDs]
Note that these files are owned by
root because they contain sensitive information, and as such,
sudo is required to be able to access or edit them. Also note that while the filenames in this path are usually the SSID, this is not a hard-and-fast rule. Therefore, you might need to do a bit of poking around to find your network.