More specifically, "full frame" refers to a sensor the same size as a 35mm film frame, i.e. 24x36mm. The 1Ds Mark II and the 5D are your digital choices in this size.
APS was a film format smaller than 35mm. Most digital SLRs are APS-C, which is a 15x24mm sensor size. Among Canon's recent cameras there are the Rebels (300D, 350D, 400D), the D60, 10D, 20D and the 30D.
So in linear dimensions the APS-C cameras are 1.6x smaller, and in total sensor area they are 2.4x smaller.
Because any given lens is casting an fixed image circle (which changes based on the focus and (with zooms) focal length), the sensor upon which it's cast determines the portion of the image circle that is recorded. This means that using a smaller sensor is effectively a 'crop and zoom' of what the same lens would produce on a larger sensor.
All this stuff is irrelevant to you if 35mm film isn't a 'reference point' for you. But what you'll see (correctly) written is that on APS-C a 100mm lens gives you the same field of view as a 160mm lens would on full frame.
EF-S lenses, again, are only compatible with APS-C, because their image circle is too small for full frame. Canon has been able to sell certain lenses for much less money than they would cost otherwise, because they can use less glass in their manufacture.
Now, I don't really understand the above recommendation about not buying EF-S lenses. If the argument is that you might some day own a full frame camera with which an EF-S lens wouldn't be compatible, realize that the cheapest full frame digital camera is between $2500 and $3200 depending on what deal you get, and there's absolutely no prospect of that price coming down anytime soon. So unless you're planning on using your lenses on a 35mm film SLR, or you're really looking into a 5D or a 1DsMkII in the near future, there isn't much downside to buying an EF-S lens. Sure, in 5 years there may be cheaper full frame cameras available to consumers for $1000 or under. But in the interim 5 years, you should get what best suits your shooting needs and budget -- and spread out over 5 years, the price of most lenses seems rather small. If the argument is that there are better alternatives to any EF-S lens, then that's a personal matter of comparing and contrasting your different options. There are cheap EF-S lenses like the 18-55 kit lens, mid-range like the 60 f/2.8 macro and 17-85 IS, and high end like the 10-22 and 17-55 f/2.8 IS. No general statement about EF-S lenses can really encompass all of these, other than their camera compatibility.