Create a new file, it'll open up portrait to begin with. Then go to File, Page setup... Choose page attributes from the top left pop-up menu, then click on the sideways guy (the one on the right) net to where it says Orientation:
If that doesn't take, go to File, Document setup... and make sure you check the button labelled "use page setup."
CV
P.S. You'll get faster responses to Illustrator questions if you post them in the new Graphics/Illustration forum. (check it out!)