Actually, the best angle to shoot a sky with those deep blues isn't with the sun at your back--it's usually with the sun at about 90 degrees from where the camera is facing. That said, you can't always get wonderfully deep polarization. Sometimes the time of day or atmospheric conditions are less than optimal.

The best thing to do is to buy a pair of relatively cheap (less than $20) polarized sunglasses and wear them. By tilting your head one direction or the other, you can get a feeling for the best times of the day and best directions to shoot an image with the circular polarizer.