When you start your VM for the first time, VirtualBox will ask for a startup disk. The startup disk should install our operating system, but we don't have one yet. Head over to https://www.ubuntu.com/ and find the server download. At the time of writing this, I downloaded Ubuntu Server 16.04.1 LTS (Long Term Support). The default download should be an iso file.
Once you have downloaded the Ubuntu iso file, start the VM. When it asks for the startup disk, you can browse your computer and select the Ubuntu