You need
Vanitygen to make vanity addresses, to do it on ubuntu you would need to compile and run it, there is a video tutorial of it here:
https://www.youtube.com/watch?v=ml2PFw7KiJU but make sure you understand what you're doing before going ahead with it and you can read more about the difficulty and the average time on the link above.
After that just print your keys and address on a piece of paper to make a paper wallet or use the bitcoinpaperwallet as suggested above. Also, make sure to test the address first offline by importing it into a wallet before sending any bitcoins to it.