I am designing a perfect bound book, I understand that the pages will all be single, so they can easily be in different paper (colour, weight etc), but I can't figure out how I can tell the printer which page will go where, should I send separate pdfs and then tell them the exact order?
Typically perfect bound uses 8-page "saddle stitch style" signatures that are then stacked, so you could bundle them as individual files of 8-pages each.
I have never done any real work with production binding (just some home projects and intro stuff) as I rely on the production staff's know-how. You can insert individual sheets and have i.e. non-multiples of 4 but I think that if the binding is just stacks of paper glued at the end, they fall out. For my BS home stuff this happens (I don't mind), but for good work, the signatures are usually clamped and ground down. Presumably, this roughs the paper and provides a better surface for the glue. Someone with more direct experience in this regard can speak to that.
I do an "ad book" that often has 2 special colors, and I bundle them as 3 individual books named using the paper color. Note that the colored pages are either contiguous or are not running pages and can be inserted randomly inside the signature without editorial issues, and the book is folded and stapled.
However: if your book is using a arbitrary random color paper on every even page, then you probably want to speak directly with the production people to work out a way to communicate how you want it. Usually you get the sales person to set up a meeting with the three of you. It really is crucial to get the person who is actually in charge of the production of the piece. The sales department will not be able to handle it properly.
If it were me, I would also provide a paper dummy of what the finished product is supposed to look like, at least for page ordering. I would bring something of this nature to the preliminary meeting and say "this is a dummy of what I am thinking, with random color order, weights etc. what is the best way to submit a file so that your production staff understands how to put it together?"