1a. Free Tools
as the name already says, these tools are free of charge so you do not need to pay for them, some functions may be restricted to the "full" or paid version.
1b. Evaluation Tools
normaly they have almost all features like the full paid version except that they will run only 30 days, or allow you a limited amount of savings or compile, or they won't let you produce certain designs that can be used for production
1c Licenced tools
well they are nomaly not limited and if you have tried some of the other two tools and think that you want this tools from this manufacture you might need to buy the full licenced version. if you want to use nios and create files for production you need a lincence. well with quartus 9.1 the nios-e does not require a licence
2 yes correct
3. no and yes
FPGA are RAM based chips so they forgett there configuration with removing the power, they need to be reconfigured again. but some fpga from other manucature have nonvolatile features.
the CPLDs like MAX II are nonvolatile
4. for altera devices, use quartus 9.1 web edition