To cleat a line, make sure first that the line is wrapped completely around the cleat at least once as shown below.
Then criss-cross as shown below.
Finally, loop over one more time, making sure that loose end goes underneath loop, and lies parallel to previous criss-cross as shown below.
A bowline is shown below. This is considered the most useful knot on a boat.
To fasten a line to something else, two half-hitches can be used, as shown below.
A better variation of this was shown to us by Peter Underwood. Begin, with a single half hitch, as shown below.
Then, wind the second half-hitch around and behind the first as shown below (brown line).
Finally, add another half-hitch (purple line). This variation does not slip at all.
A clove hitch is shown below. This isn't such a great knot as it slips easily unless there is tension on both ends.
A reef (or square) knot is shown below. This is great for tying a bundle.
A rolling hitch is shown below. This is good for tying one line to another (in order to remove a winch override, for example).
For more info on useful knots, refer to Chapman's 62nd edition, pg. 284. Also, the Boy Scouts have information about knots on this site.