EF-S is the type of mount your camera has, which is common to Canon's 1.6x crop dSLR consumer/prosumer cameras. It supports both EF (full frame) and EF-S (cropped) mount camera lenses.
An EF-S lens has an extra protrusion in the back, and the EF-S body has a space to accept this. This space is available because of the smaller mirror box that a 1.6x crop camera has. A full frame (EF mount) camera won't have this space and can't accept an EF-S lens. But they're not that common (nor are they cheap) so I don't expect you having to worry about this issue.
I don't have any IS lens recommendations since I don't have any experience with IS lenses in that range.
-18-55 IS ~$180 - A step up from the kit lens and it adds IS if you like the range the kit lens gives you.
-28-135 IS ~$450 - Another step up, with a bit longer range but it lacks the range on the wide end.
-17-85 IS ~$500 - Similar quality to the 28-135, but it has less on the telephoto end and more on the wide end.
-17-55 IS ~$1000 - Awesome lens that is another step up from the above. Very good quality, but smaller range and much more expenisve.
Another option if you are Ok with third party is the new Sigma 18-200 OS super zoom. The OS version has optical stabilization (like IS) and is one of the best super zooms out there. It is a bit more of a compromise since it has such a large range, but it is a step up from the kit lens and you can get great results with it. It is ~$500 as well.
The trade off for all that zoom range you are getting is that if you want a long/flexible/cheap lens you give up aperture speed. For most people IS isnt all that big a deal at normal focal lengths and you are much better off with something like a Tamron 28-75 F2.8 for about $350
Of course if you are still in green box mode you wouldn't ever get the benefits of fast glass, so it really depends on what you know about SLRs and how willing you are to learn new things...
Is IS important? On a longer focal length lens shooting indoor, still objects, IS can make the shot possible hand holding. I just got the IS version of th 70-200 F4. I can take sharp, clear pictures of indoor objects at full zoom 200mm x 1.6 = 320 at 1/20 shutter speed. Handheld. That wasn't possible with the non IS version. Long focal length lens without IS, you would need to take shots under good to very good light condition (outdoor and not too overcast) hand holding.
I don't discount the value of IS. It's terribly overpriced on first party gear tho and as more third parties add competitive solutions and other camera manufacturers add it into bodies it will cease to command the premium it fetches for. Now on longer lenses for sure I think the IS is truly beneficial and worth the price premium that Canon gets for it.
I'll put the optical qualities of the Tammy 28-75 up vice the Canon 24-70 2.8 or the 24-105F4IS any day tho and be happy paying a third of the price for that lens. Even if the canon lenses are moderately better they arent 3x as good to me.
I also have the 17-40F4 and love it on both my crop camera(20d) and Film (obviously Full frame) EOS1, and I have never ever wished for IS on that lens...
Also, and this isnt clear to photo noobies: even if the IS allows you to handhold a shot at 1/20th of a second that only allows you to take clean shots that don't have any moving objects in them! At 1/20th of a second you are gonna have a LOT bigger problem with motion blur than camera shake on a wide lens!