1. Privatekeys are normally stored in the medium that generated the Bitcoin address? i.e. if I make a new wallet in Multibit, that private key is stored there.
Correct.
If I make a new wallet on Mtgox, then the private key is stored there?
Since those private keys belong to MtGox, they get to decide how they are created and where they are stored.
2. One private key is integral to moving funds for an address.
Yes.
How does the Elliptic Curve Digital Signature Algorithm, know that only that address works?
It verifies the digital signature with the public key.
Is it theoretically possible for other private keys to work as well to move funds?
Theoretically? Yes. But the odds are astronomically small. For all intents and purposes you can consider it impossible.
3. If I have a private key, and I don't know the public key, can I still make transactions?
Yes. The public key can be calculated from the private key.
If so, does anything prevent someone from randomly accessing potential private keys and hope to steal someone's money?
Yes. The same thing that prevents all the air in the room from gathering together in one corner and suffocating you. Specifically, astronomical odds against the possibilty.
4. I'm told to keep my bitwallets in an unconnected device. How am I supposed to spend them though?
For the safest possible long term storage, offline is recommended. A system must be connected to transmit transactions. The private keys can be kept offline and just the signed transaction can be brought to the online system. This is how Armory works.
