This question gets asked a lot, so I'll answer it here definitively:
Yes, you can embed videos into AWPCP easily.
First, you have to make sure you follow the WordPress.org embedding rules. Only certain sites are allowed (by WP whitelisting and this can't be changed unfortunately) and you have to use the short code to do it. The full details are outlined here: http://codex.wordpress.org/Embeds
After that, AWPCP supports this in the Description field of the ads only. Other fields don't expand the short codes you enter, so be sure to place the videos in there.
Once you do those two things, videos should work within the classified ads, no problem.