There is no really easy, painless way of doing this, unfortunately; and certainly not with the default Ubuntu software.
Assuming you have the same version of Ubuntu on both computers (this won't work if you don't, and tou'll have to try slightly more difficult methods): the most foolproof way, though it is inelegant, is to install ubuntu-restricted-extras and VLC on your machine that does have internet access.
Then, copy the contents of /var/cache/apt/archives onto a USB memory stick. Go to the un-connected computer & plug in the memory stick, and copy those files into that computer's /var/cache/apt/archives directory. When you've done that, open up a terminal (ctrl+alt+t) and paste in the following commands, one line at a time. You'll need to enter your password at least once.
With that done, you should be able to play back those formats.
sudo apt-get update
sudo apt-get install ubuntu-restricted-extras vlc