It is true - as a part of H1B application you need to post a job advertisement in some US job board first, which becomes a part of the documentation you submit to USCIS. I went through that as a part of my own visa process.
EDIT: ok, maybe my immigration lawyer was a weirdo :)