Your computer is not running at 800x600 in that video. There are two separate settings that need to be made to make the game run fullscreen at 800x600. The very first time you launched the game, it gave you this dialog box:
If you select "Always Switch Resolution" or "Switch Resolution This Time", it will change your screen resolution to 800x600 while running the game. If you select "Never Switch Resolution" or "Don't Switch This Time", it will keep your current screen resolution and run the game either in a window in the middle of the screen or letterboxes, depending on your settings. If you select "Always Switch Resolution" or "Never Switch Resolution", you will never see this box again. In order to play the game fullscreen without letterboxing, you need to set it to always switch or switch this time. If you had set it to never switch in the past, you can change that by going into the in-game preferences by clicking the floppy disk button in the lower right and clicking the box labeled "Ask at startup whether to change resolution."