There are two ways, due to the limited HC-06 AT command set and lack of hardware support (This varies by revision or carrier board, your milage may vary). I got my limited information from http://mcuoneclipse.com/2013/06/19/using-the-hc-06-bluetooth-module/
The first is by connecting to the high end of the led on the carrier board (or to pin 24). If it is blinking/switching on and off, it is not paired. If it is a steady high/solid light, you are paired to the pc.
The second is to send an AT command. For example, if you send
AT when not paired, you will get back
OK. If you send
AT while paired, you will not get a response. You can use this to know what is happening.