I've got the parallel flash working now (the 128P30 on the Cyclone III starter board). I worked it out with Altera support (thanx guys).
In qsys. Make sure you include a Tri-State Conduit Bridge and a Generic Tri-State Controller. In the Generic Tri-State Controller you'll be able to select which flash you are using. Those two were all I needed for interfacing with the flash. (see attached image)
Make sure you set the 0th line from the address bus from nios II to xxxP30 flash to be virtual. You can do this by ignoring that pin in the pin planner and adding this line to your .bsf file:
set_instance_assignment -name VIRTUAL_PIN ON -to <your_address_bus>[0]
If you are using the 128P30, qsys will give you a 24 pin bus <your_address_bus>[23..0]. So we use <your_address_bus>[0] for virtual then use <your_address_bus>[23..1] to connect to the first 23 lines of your CFI flash (1-23). (For the 256P30, you only connect 24 pins, and for the 512P30, you connect all 25 pins). See attached image.
For programming FPGA configuration, follow the directions in the appendix of Cyclone III FPGA Starter Kit User Guide. For programming software, just open nios II flash programmer, add new, point to .socpinfo file for nios II qsys design, add the .elf file, and click program.
Disclaimer: I'm a beginner so there may be problems in the above method although it worked on my setup.