How do cognitive scientists measure creativity? Einstein said once something like creativity is more important than intelligence. Intelligence as it is measured is really one's speed and efficiency at processing information. How one processes the information is the 'province' of creativity. 

Are there any effective, psychologically-approved tests that measure creativity and ones capacity for interesting or clever creative associations between sets of ideas?
The Torrance Test of Creative Thinking is a good place to start.  It scores for fluency (number of responses) as well as originality (statistical rarity of responses) and elaboration (level of detail) on a variety of different tasks. The validity of the TTCT has been examined with several long-term studies, so there is a fair amount of data on its measurements as well as the form of the test itself.

Torrance, E. P. (1981b). Empirical validation of criterion-referenced indicators of creative ability through a longitudinal study. Creative Child and Adult Quarterly, 6, 136-140.