Video loads in the same way as pictures, you navigate to the folder that contains the video, drag it into the arrangement.
Now, if this video is in a format the program cannot read or requires a different codec, then you might need to make an additional purchase. I think that would be true on like MPEG-4 video.
At least that is how it works in the PhotoStory 9 & 10 that I have.