That would be paralax scrolling. You've got the general idea right, though. You just need to keep a few variables to keep track of the "camera" x,y position, as well as the background's offset. When you move left or right, the camera's x position is increased/decreased by a rate of 1 * speed, and the offset by a rate of 2 * speed. When drawing, you want to draw everything in relation to the camera.

If you don't understand that, then you might get this. Let's assume your screen is setup in 800*600. Your map goes from 0,0 to 2000,4000. When you move right, the camera's X variable would increase...Let's just say you moved it 100 pixels. If you wanted to draw something in the camera's view, it would be the object's X variable - 100 (camera's X value), right? You should also make sure an object is within the view( > camx && < camx + screen_w ) before trying to draw it, since if it's offscreen it won't be drawn anyways. Likewise, you need to make sure that you do not move the camera below 0, or above 2000, since those are the map's boundaries.

I realize I'm probably rambling a bit, but maybe some code would help.

Move the screen:

Draw background:

void DrawBackground(BITMAP *dest, BITMAP *bg)
{
  // draw a tiled background, offset by camx,camy
  for(int b = 0; b < (SCREEN_H / bg->h); b++)
  {
    for(int a = 0; a < (SCREEN_W / bg->w); a++)
    {
      blit(bg, dest, 0, 0, a * bg->w - (camx % bg->w) + bgxoffset, b * bg->h - (camy % bg->h) + bgyoffset, bg->w, bg->h);
    }
  }
}

Draw our player

void DrawPlayer(BITMAP *dest, Player *pl)
{
  masked_blit(pl->Sprite, dest, 0, 0, pl->x - camx, pl->y - camy, pl->Sprite->w, pl->Sprite->h);
}

My code may contain errors, but you get the rough idea.