Now, the only time I used Keynote, was for an iPhone presentation for Steve Jobs... the client who created the slides and video basically asked for the same thing as you.
So here's what I would recommend...
First, make the document the size of the display you're going to view it on. Import the video into the slide. Once it's placed in there, scale it to the full width of the slide (Note: keep the shift key pressed down to scale proportionally). Now, depending on the aspect ratio of your video (i.e. 4:3, 16:9, etc...) you might have some blank space top and bottom. In this case, I just make the background black or white, depending on the design.
Yep, I just checked again to be sure, but it's as simple as dragging the video into your slide.
To go full screen, set the width of your video the same as the width of your slide. The easiest way is in the info panel (the "ruler" pane) and (make sure the maintain aspect is checked) type the desired width. You can then drag the video to the middle of your slide (with the snap lines).
You could also stretch the video or crop it to make it fit perfectly inside your slide, but I think black borders are a better solution.
In the Quicktime pane of the info panel you can choose wether to repeat the video or not and what still frame is used when the video is not playing (normally the first one)