This is specific to Canon, but what is the difference between EF and EF-S lenses?
EF-S lenses are specifically designed for APS-C digital bodies and optimized for the fact that they have smaller sensor and mirror. EF-S lenses are marked with a white square on the mount instead of a red dot that EF-glass has, and can be only used on EF-S compatible bodies (almost all of smaller-sensor Canon DSLRs, up to EOS 7D).
Film and larger-sensor digital cameras (5D, 1D, 1Ds) take only EF lenses. If you have a camera with EF-S mount support (such as EOS 7D, 50D or 500D), you can use both EF and EF-S lenses.
The "S" in EF-S stands for "short back focus", which means that the rear element of the lens is closer to the image sensor than on regular 35 mm SLR cameras. The proximity of the rear element to the image sensor greatly enhances the possibilities for wide angle and very wide angle lenses, enabling them to be made smaller, lighter (containing less glass), faster (larger aperture) and less expensive. Most current Canon EF-S lenses are wide angle.
Any EF fit lenses you own (usually marked with a red dot near the EOS mount) will work fine with the 5D mkII
Any EF-S fit lenses you own (usually marked with a white square near the EOS mount) won't work or fit the 5d mkII, as these are designed to fit crop sensor cameras like the T2i and not full frame sensors like the 5D mkII
As an addition, some non-canon brand lenses designed for crop sensor cameras do still come with a EF mount, so they will fit on a 5d mkII, but often won't fit the full frame of the image. I have a Sigma 8-16mm that is EF fit and you can see the lens hood on a full frame until you zoom in to around 14mm. It works fine however
EF-s lenses are a slightly different format whereby the rear element sits closer to the lens, this is possible due to the smaller mirror with APS-C sensor. The distance from the back of the lens to the image plane is known as the back-focus distance, hence the s in EF-S standing for short back focus. Other manufacturers have lenses designed for smaller sensors with appropriately smaller image circles but they don't have a different back focus distance.
Having the lens sit slightly closer does make it slightly easier to design wide angle lenses, however I've heard the reason Canon introduced EF-S lenses was so they could scale down existing lens designs as a base for the optical design to avoid having to start from scratch. Hence the EF-S 60mm macro is a 1:1.6th scale EF 100mm macro etc.
It's often said you can't use EF-S lenses on a full frame body (such as the 5D, 1Ds) but this is not strictly true. Canon use a different shaped rear baffle to physically prevent you mounting as the mirror could hit the lens and cause damage. However this can be removed to allow mounting, and since the rear element moves when zooming there are positions that allow shooting. Vignetting is a problem as EF-S lenses project a smaller image circle, but again the image circle can get bigger while zooming so some focal lengths work ok.
Using an EF-S lens on a full frame body would be extreme however the 1.3 crop APS-H sensor of the 1D line is quite amenable EF-S lenses, and the Canon EF-S 10-22mm in particular. Whilst you can't go wider than 12mm, you do get a 12-22mm providing a sorely needed ultra wide option for the 1D. You do get some vignetting at 12mm, which can be fixed apparently if you Dremel off the filter threads :-O
EF was the mount for the new EOS system that replaced their FD mount in 1987.
EF-S lenses are specifically designed for the smaller APS-C sensor size, like on the Rebels. They're not compatible on full-frame cameras. These cameras have a white square on the mount's surface, along with the typical EF red dot that all EOS cameras have.
The EF-S lenses are specially constructed for cameras with smaller sensors, so it can't be used on a camera with a full frame sensor. That back lens of an EF-S lens is further back, so the mirror of a full frame camera would hit the back of the lens.
An EF lens is made to cover the full frame, so it will also work on cameras with smaller sensors.
The image circle of an EF-S lens is smaller than the one of an EF lens, to correspond with the smaller sensor. When you use an EF lens on a camera with a smaller sensor, you will simply use a smaller part of the image circle. This has the positive side effect that it will reduce the vignetting significantly.
Generally an EF-S lens is cheaper than the corresponding EF lens, as it can be constructed with smaller optical lenses, and it can make use of the extra space inside the camera given by the smaller mirror.
Small sensor Canon DLSRs will accept both EF-S and EF lenses, but canon made it physically impossible to attach a EF-S lens to the full frame cameras (5D & 1Ds) (due to mirror interference as @Guffa points out). This makes the Ef lenses more versatile as they will work with all canon EOS cameras.
If canon ever make full frame sensors standard on its DSLRs your collection of EF-S lenses will be worth a lot less. This is probably part of the reason that there is no EF-S "L" lens. The LONG-term resale value of EF-S lenses are a bit more doubtful than EF lenses.
Some of your lenses might be usable on the 5D; others might not be.
Specifically, any EF lens will be usable, but EF-S lenses won't be (see this question for the details). EF lenses have a red dot by the lens mount, and EF-S lenses have a white square.