How are 360° photos stored and processed?

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.

A lot of these images that are made for commercial purposes, e.g., real estate walk throughs, are either cylindrical or spherical projections, and the method will depend on the requirements of the hosting environment. Many of the online hosting services have propriatary software, and have slightly different requirements. Whether a cylindrical or spherical projection image is chosen depends on the marketing budget for a particular property. A spherical projection image requires triple the number of individual (pre-stitched) images as a cylindrical projection image, and so costs more to produce. The answer mentioning other (non-typical) projections is spot-on. It would be only a matter of working out the mathematics. Virtually any 3d space would be possible once the conversion algorithm is determined. (A projection on a Klein bottle would be an example that might prove more difficult!) Any Euclidean 3d space should be rather straightforward.