The entire blockheader (which includes the nonce) not just the nonce is hashed using the SHA-256 algorithm. Now the blockheader is actually hashed twice to produce the block hash. Block Hash = SHA-256(SHA-256(blockheader)).
For more info on what is in the blockheader (Looks like the wiki is down so here is a google cache).
http://webcache.googleusercontent.com/search?q=cache:FZ9pUxR3ldEJ:https://en.bitcoin.it/wiki/Block_hashing_algorithm+&cd=1&hl=en&ct=clnk&gl=usOf course it is trivially easy to hash a block header. The average GPU can do this almost a billion times a second. So not all blockhashes are solutions. There is a target based on the current difficulty. The blockhash has to be smaller than the target to "solve" the block. So a miner will take a blockheader starting with a nonce of zero, double hash it check against the target. If it is too large, it will increment the nonce by one, and do it again. Eventually all ~4 billion nonces will be tried, so the miner will make some other change to the blockheader and start over again at zero. The miner does this until someone publishes a new block on the network.
Currently difficulty is ~30 million which means the target is so small that it will take on average 128 quadrillion (2^32 * 30 million) hashing attempts before a block hash is found which is smaller than the target. When a miner finds hash which is smaller than the target it produces a valid block (sometimes called a block solution or "solving a block"). The miner relays the new block to its peers, who relay it to their peers, who eventually relay it to every node on the network. All miners then construct a new blockheader using the just found block as the prior block and start the process all over again which they have done 249,913 times. It is written this will continue until Great Satoshi returns to judge the crypto and the fiat.
Imagine it like a dice game which requires you to keep rolling a bunch of dice (say twenty) until you get a certain number of "ones", the difficulty would determine how many ones are needed to "win" and how long on average it would take. Difficulty =1 would be pretty easy, difficulty = 20 would be insanely hard.
