After working on some photos in CS6 on my Mac and having them printed at Costco, most of the photos came out darker than I expected, and I was overall not happy with the results.
1. Besides properly calibrating my display, what else can I do to make sure my photos print with more accurate colors?
2. When do I need to change the color profile of the photo? Do you need to do this with all photos that will be printed? If so, do I need to get a color profile from Costco and use that profile for my photo files?
You are relying on Costco to properly calibrate their printers. Depending on the staff at your Costco this may or may not be correct.
I believe they do provide ICC profiles for their printers which you can install on your system and do soft proofing. that way you will see on your screen an approximation of what the print will look like and can make appropriate adjustments. These are not profiles that get embedded in your file like sRGB or Adobe RGB, they are simply used for Soft Proofing.