You probably want to look into using the SDL_SoftStretch function. If you have a source 16x16 SDL_Surface* called (for example) image_16square and a destination 64x64 SDL_Surface* called (for example) image_64square you would call it like this:

SDL_SoftStretch(image_16square, NULL, image_64square, NULL);

Untested. This uses SDL 2.0. If you're using SDL 1.2 you should specify. Basically you'd lock both the 16x16 source surface and the 64x64 destination surface. Then you'd go through every pixel in the 16x16 surface and set the equivalent 4 pixels in the destination surface to the same value as that pixel.

If you are doing scaling, or rotating, I would suggest not do anything in SDL as it is all done in software, and will slow down your PC terribly (at least using the released SDL 1.2). I would suggest looking at SFML as it does all scaling and rotating natively for you in HW.

In the long run, you'll be happy you switched IMO (not just for graphics, but for the other interfaces it provides).