Additionally, the iPhone 3G (and later) has a true GPS receiver built in, so provided it has line-of-sight with enough GPS satellites, it can get a fix on your location even in the absence of WiFi signals. (And using GPS, is it would get a better fix than it would using WiFi or cell towers alone anways.)
Note that the iPhone's GPS receiver is optimized for A-GPS (Assisted GPS) where it uses the cell towers to obtain information about which satellites should be nearby at any given time, thereby speeding up the time it takes to get its initial location fix. In the absence of cell towers, the GPS receiver is still capable of operating standalone, but it would take several minutes to a half an hour to obtain an initial fix, rather than a few seconds.
By the way, even in secured WiFi connections, the MAC addresses are always transmitted without encryption. All the Skyhook database needs is the MAC addresses and relative signal strenghs, nothing else, so WiFi location services can function even if you don't have passwords for any of the nearby networks.
