Hashing is a function from some bit string (usually variable length) to another bit string (usually smaller, and of fixed length).
Hashing is used in databases for data retrieval, and in in-memory data structures called hash tables. It allows us to reduce arbitrary data, such as a character string or a complicated object with many fields, to a binary number which can then be used directly as an index into a sparse array to fetch the associated data (with some details for handling hash collisions).
The hashing functions used in the above manner are "cousins" of cryptographic hashing functions. They are designed to different requirements. They must be fast to compute, and achieve a good distribution.
In secure computing, cryptographic hashes are used to digest data into some representative, small bitstring. Cryptographic functions have different requirements. They are designed to be difficult to reverse (to be "trap door" or "one way" functions). Not only that, but an important requirement is that it has to be difficult to find, for a given plaintext and hash value, another plaintext which produces the same hash.
Hashing can be used not only for passwords, but as a checksum for verifying data integrity and as part of the implementation of digital signatures. To digitally sign a large document, we simply have to hash the document to produce a "digest" (a name used for the output of a hashing function, when something very long is hashed). Then just this digest is put through the public key crypto-system to produce a signature. You can see the weakness there: what if an attacker succeeds in producing a document which has the same digest? Then it looks like the original signature produced over the genuine document is actually a signature of a counterfeit document: a signature-transplanting forgery has been effectively perpetrated.
Password hashing allows systems not to store the plain text version of a password, yet enables them to verify whether the user trying to gain entry knows that password. Not only does hashing allow systems not to store the plain text passwords (which would have to be very carefully guarded) but it allows for the possibility that even if the hashes are publicly exposed, the passwords are still secure (similarly to how public key crypto systems are able to reveal public keys). Though in practice, hashes are nevertheless protected from public access: for instance
/etc/shadow files on Unix-like systems, supplementing world-readable
The hashing function is anything but random. However, randomization is employed to thwart attackers who build large dictionaries of passwords and hashes, that enable them to look up a hash code and retrieve the corresponding password.
To hash a password more securely, we can simply add some random bits to it called a "salt". Different salts added to the same password, of course, lead to different hashes (hopefully with few or no collisions).
If the random salt is, say, 32 bits wide, it means that, in theory, one password can hash in over four billion different ways, making it very impractical to have a precomputed dictionary of all possible hashes of a large number of passwords.
Of course, when the user is being authenticated, she does not know anything about this salt. That is okay because the salt is stored along with the hash in the user's profile (often, combined with the hash into a single compact bitstring). When the user's password entry is being validated, the salt is added to whatever password she entered, so that the hashing is carried out with the correct salt. If the password is correct, the hash will match, since the salt being used is the right one also, having been pulled from the user's profile.
So that is how randomness is incorporated into password hashing, while still allowing it to work.
What makes hashes hard to crack is that they are built from "trap door" or "one way" functions. In mathematics, there are many examples of such things. For instance, simple addition is a trap door. If we add some integers to produce a sum, it is impossible to recover the original numbers, knowing only the sum.
Password hashes are not encrypted passwords. If an attacker has the hash and salt of a password, and happens to guess the password, then she can easily confirm this, exactly in the same way that the login authenticator software does it: she runs the password plus salt through the hashing function and sees that the correct hash emerges.