Is something missing from my Macbook Air package? Should my brand new Macbook Air 13'' have come with a CD/DVD in that black booklet included in the package?
No. The mid 2011 air uses Internet recovery to network boot and reinstall lion. 

You can use the recovery hd assistant to make your own USB media for booting if you don't expect to have Internet when you ever need to restore your air.