I am not aware of anyway you can do this in Fritzing because Fritzing does not allow holes to intersect the edge.
The place I have make my boards charges an extra $15 for them so I have never bothered to figure out how to do it since that is more than 3 times the cost of the PCBs at $4.90 for 5@ 100mmx100mm. I usually just make finger joints (same as the castellated but with vias connecting both sides and not right at the edge) and they are easy to solder you just have to make sure you get some solder under them like soldering a QFN package.
If you must have them castellated I can think of two ways.
(this one will work for sure) Make your boards a little larger than needed and then cut the edge off yourself. I have done this with Arduino Pro Minis to mount them easily on custom PCBs.
(up to your board shop if they will do this) First you create your PCB larger then needed to ensure the holes are exported during Gerber export (check with a gerber viewer like Gerbv). Once you have them exporting correctly and have saved the gerbers you would reduce the size of the PCB in Fritzing until it cuts off the holes and then export the gerbers again and use the drill layer ( and possibly the copper layers if they are not complete on the second export) from the first export with the other layers from this export. That should give you a set of files capable of creating a castellated PCB.
There is a discussion about how to create a castellated board on stack exchange that you may feel like reading.