To directly answer your question, I agree with Iggy, caulk first, then seal.
My long response is going to be different however:
Steps:
1) Clean excess caulk
2) Clean edges to be caulked with acetone (or if you have natural stone, methyl hydrate, or even weaker, alcohol if you have sensitive materials)
3) Allow a few moments for the cleaner to evaporate (prep for caulking)
4) Caulk using type 2 silicon, do not fill the gaps (more on this later)
5) Allow to caulking to cure and you're done
Why you use type 2 silicon: It has an additive to kill off mold and mildew, should the cleaning not have been amply thorough it will kill it off (avoiding one reason for caulking failure.
Why you caulk only two edges: If your house is constructed with wood (like most) there will be expansion and contraction, a major reason for caulking failure (the major reason is the surface is unfit for caulking) is because the caulking is attached to more than two surfaces, causing it to be pulled away from the perpendicular surfaces.
Why you don't use sealants: Unless you have natural stone, the grout is extremely resistant to staining (and has been for about eight years now) while tile doesn't stain (again, unless it's natural stone).