>>"So my question is, do they come preshipped with a bootloader?"
-->Cypress PSoC is not shipped with Bootloader by default. The customer has to program the Bootloader and Bootloadable projects in case he wants to use the Bootloader feature.
>>"Is there something we have to do to them before we are able to flash something to them like install the bootloader?
--> No. You can directly program.
Please go through PSoC progamming/Debugging troubleshooting guide from the link below.
After going through the above kba if still the issue is not resolved, then please attach the project and the complete schematic of the board for us to check at our side.
Please compare connections of your board schematic with our development kit schematic.