How are 360° photos stored? Do they have a special file format or are they projected onto a regular png/jpeg?

360x180 panos are stored a number of different ways, but most commonly as a single image in the usual visual file formats (TIFF, JPEG, PNG) in equirectangular projection. Equirectangular projection represents the sphere as a 2x1 rectangle, where the cartesian X-Y coordinates correspond to the longitude and latitude of the point on the sphere. As a result, there's a lot of warping around the poles.

When displayed interactively, that equirectangular is most commonly used as the basis for either HTML5 or Flash output; the older Apple QuicktimeVR format was another standard, which used a cubemap rather than an equirectangular projection as a basis. Cubemaps most common are done as a 3x2 grid of the faces, or as a cross layout (e.g., Blender skyboxes and environment maps).

The Google cardboard format is two stacked equirectangulars for 3-d; left-eye view over right.

If they are projected onto a flat image will they lose quality in some areas where the spherical projection has warped the image?

Depends on how you plan to view and rewarp to another projection.

Are there any non standard ways for storing and processing 360° photos which work differently to the common methods?

Tons. There is no standard. And remapping is kind of a sport among those who do 360x180s. Cartographers have figured out a lot of ways to represent a sphere on a flat surface. :) Just looking at the list of Flexify mappings should give a sense of how many possible mappings there are. Some common ones you'll see are stereographic little planets/tunnels. But sky's kind of the limit. I like using drostified quincuncial when I really wanna screw with peoples' heads.

See also: the pano-projections tag.