Software Advice for producing video ads
That is motion graphics.  A program like Adobe After Effects in combination with Photoshop or Illustrator is ideal for producing such a video.  Something like Flash could also be used.

Note that it is very complicated to make something that good on your own.  There are however templates available for After Effects that you may be able to use.  Alternately, you could look for someone who knows how to do motion graphics and hire them to do something.