The upholstery grade of velvet should be a heavy cotton velvet. Check your local yellow pages, there are stores that sell specifically drape, curtain and upholstery, but they are few and far between.
Do be very very aware that velvet has a nap. If you're not familiar with the term think of a cat. If you rub it head to tail you're going with the nap, rub it the wrong way and you're going against the nap. You can feel the difference...right before the cat claws you.
Every piece of your velvet must be put in so that the smooth direction is downward. There is more waste when choosing a fabric with a nap as opposed to one that doesn't have one. (However it's my personal opinion that whenever you're doing upholstery act like the fabric HAS a nap even if you can't feel or see it.). If you're planning to cover the wall, too, you'll probably want to get heavy flexible plastic or posterboard, and attach the fabric to that, then glue that to the walls.
I've shopped at a chain called "Calico Corner" and also Jo-Ann Fabrics has a lot of upholstery stuff. You'll probably have to special order it.
Today is a gift, that's why they call it the present.