If using iOS4.0.1 or lower, simply visit
http://jailbreakme.com on the iPhone's browser & follow the instructions.
There are also other methods for earlier iOS versions & other devices.
iOS4.0.2 & above cannot be Jailbroken using
http://jailbreakme.com, as iOS4.0.2 patched the PDF exploit used by the site to perform the JB. Other holes still exist, however, & there should soon be a programme for Jailbreaking iOS devices running iOS4.1 (current version) via connecting it to your PC/Mac (like previous Jailbreaks, prior to the
http://jailbreakme.com method).
The iPhone Dev Team are the main Jailbreaking guys, & have a lot of info at their site:
http://blog.iphone-dev.org/
Wikipedia entry all about Jailbreaking:
http://en.wikipedia.org/wiki/IOS_jailbreaking
EDIT: Oh, & although not illegal, it *does* void your warranty (if Apple find out). It can be removed easily enough though simply by restoring the firmware via iTunes.