I want to view and edit some map-like data (obvious things like points / paths / polygons / bitmaps with annotations; also quad-tree masks but I can convert them to something else if needed) in custom format and GIS programs like Qgis seem just fine for right with it.
Which formats should I be exporting data into? If possible I'd like to be able to easily parse user-modified data back as well. GIS world seems to have far too many weird formats, so I don't even know where to start.
ESRI Shapefile format is quite simple to implement and while I have not worked in the GIS market for nearly 15 years now, I believe it is still quite a common format.
For better or worse, shape files are still around and the format is published. They are also accepted by pretty much all GIS and serious utilities.
It is a binary format though, and the files tend to quickly accumulate as you need a set of files for each data type and shape.
KML has been mentioned above. This has become a defacto standard and is XML based - ie. Easy to write. It is designed for annotation though, and this can be limiting for many GIS applications.
Another format worth looking at is GML. It is another XML format, but as with XML itself it is perhaps too flexible for it's own good. Before writing a GML exporter, I would choose a target system and then write for it's vocabulary and implementation.