It's actually just like it sounds: your yarn goes over the needle. When you're to the point at which you're supposed to add a YO, you take the working yarn and wrap it around the right needle one time.
There's a good video of it here on the KH site:
The increase will leave a "hole" in your knitting. They're often used for decoration as well as a simple increase.
At the beginning of the row it's worked the same way. Basically, you wrap the yarn around the right needle before you even knit the first stitch off the left needle. Instead of a hole in the middle of your work, you'll have a little loop at the edge of the work.