What is a scalable image? If a client wants his logo to be "scalable", what exactly does that mean? Can I create it as a regular logo, and then just save it as .svg, or do I have to create the logo in a certain way?

He would like the image you provide him with to be of a high enough resolution that he can, perhaps, use it on a business card, on a flyer, or on a business sign, or even a poster depending on how he wants to advertise. It would help you to know something of how he will use this image.

So, your goal is to make the image as high-res as possible, with no compression, and using an image format that will carry this 'pliability'. I've typically used the 'Tiff' format for this. I'd recommend you research the 'Tiff' format, just to satisfy yourself and to confirm with your customer that he/she can use that format. (they may want you to explain its attributes) Some image hosting sites don't support 'Tiff'.

@sauvedesign- you mentioned SVG in your post. SVG's, or Scalable Vector Graphics, are created using mathematical formulas, so they are quite different than the other image formats such as jpg, png, etc.. I don't think the client was referring to that type of graphic. I would agree with BigPaw that its most likely that the client does not want a low resolution image.

In any event, if you are interested in learning more about SVGs, I have an overview and SVG samples (if you use your browser's -/+ zoom feature, you can see how the SVGs are actually scalable and do not loose any quality). HTML5 - Scalable Vector Graphics (SVG) Overview

You should note that most of the web browsers that are in use today have support for displaying SVG images- Internet Explorer 9, Firefox, Opera, Chrome, and Safari support SVG.