How do I package an existing VM that was not created using vagrant up command?

The important thing to realize (and the vagrant docs are not overly clear on that) is that there are two “flavors” of packaging:

1. The packaging guide in “getting started” you are referring to assumes you have started from a vagrant base box and initialized it with vagrant up, which you have not. This allows you to package any customizations you have made to a vagrant base box.
2. If you start from scratch or from a “plain” VirtualBox VM, as you do, you need to create a vagrant base box. You should be fine following the guide, which is based on Ubuntu.

There’s a detailed guide for creating vagrant boxes from scratch using Oracle Enterprise Linux, which might be helpful. You could also try VeeWee.

Alternatively, you could start with a Ubuntu 12.10 base box and port your customizations, in which case you could use the simpler first way of packaging.

Update

The above refers to Vagrant 1.0. Things have changed slightly in 1.1 and in particular the docs have been rewritten:

1. The vagrant package command allows you to package any customizations you have made to an existing vagrant base box in the same way as in 1.0.
2. The documentation for creating base boxes with VirtualBox has been removed in 1.1, but the docs suggest the process has stayed the same, but now an additional metadata.json file is required as Vagrant 1.1 supports multiple providers.