They are talking about all the fonts you use. If you use anytype of font in Illustrator, just highlight it and go to TYPE...CREATE OUTLINES.... and it will turn the font into shapes. If you don't do that, then when they go to open the AI file and if they don't have the font (which in this niche artwork they probably don't), it will substitute something like courier for yours. That's bad.
As for saving as a PDF, go to FILE...SAVE AS... and change it to PDF. Make sure you pick Adobe 4.0 compatibility! Kinko's doesn't officially support 5.0...and can screw things up at the printer. They really need to get with the times because now there's acrobat 6.0 out.