You didn't say which VM software you are working with so I'll keep this answer very general.
Note that there are far more efficient and cleaner methods but they are heavily dependent on the virtualization solution you're using. Check the documentation for imaging/cloning/snapshotting methods supported.
You should create a new VM disk image, install and configure Ubuntu completely to your liking but only settings which you want on all newly created VMs.
For example: omit network settings, don't add a user unless the username/uid happens to be the same every time you create new VMs.
Once you have your base VM set up, shutdown the VM.
On the host workstation you created the VM on, mount the filesystems from the disk image and zero out the free space in each partition.
This will do it on Linux host:
mnt is the mount point of where you mounted the VM disk image's partitions, which depends on where you actually mounted it.
dd if=/dev/zero of=/mnt/zerofile bs=1M conv=sync
rm -f /mnt/zerofile
Once complete for each partition of the image, you can compress the image with your favorite compression utility.
xz -9 /path/to/disk.img
Now you can decompress copies of an almost configured disk image and finish the customized settings and deploy.