How many Chinese characters have multiple readings/pronunciations in Mandarin?
There are official lists for this. See the following pages in the Chinese Wikipedia:
普通话异读词审音表 for mainland China
國語一字多音審訂表 for the ROC (Taiwan)
Neither of the lists is complete; they are basically there to provide standard answers to test students on correct pronunciation.

How many characters have variant readings is actually quite hard to answer; one reason is the large number of 'literary' readings which are still often used when reading or reciting older literature.  Chinese opera of all varieties typically uses such readings.  This phenomenon (called 文白異讀) is quite extreme in some dialects; in the Minnan dialect for example, there are variant readings (sometimes multiple variants) for almost every character.

Note: Here is the official version of 普通话异读词审音表 from the 国家语言文字工作委员会 (State Language Commission). They don't seem to have a pdf version, but you can copy the text from places such as 百度百科 (here). 

All those characters where the list says 统读 mean that those characters 'used to' have different readings in earlier versions of the list. Now through a wave of the SLC's magic wand, they have miraculously disappeared. Actually many (most) people continue to use them, but For your HSPK you may skip them.  This is one way to pick out the first ones to learn.

The ROC list is much longer than the PRC list, because it reflects more of the 文白 differences.  Be sure to keep the ROC and PRC readings separate! A number of the differences between the two standards are because the PRC simplification process has merged two different forms with two different readings into one form with (still) two different readings.