Here's my take on it. A pixel is not a square, and it isn't even a rectangle. A pixel is a point (infinitely small) that has a color associated with it.
The only way I personally have ever seen pixels viewed (interpreted) by a display is to use "nearest neighbor" sampling where the pixels were on a rectangular grid, which means that the color of any given space on a display is the color of the pixel that it is nearest to.
This is a fancy way of saying "pixels are rectangular and laid out on a grid", but stay with me on this :P
As a result, image formats have their pixels stored in a grid as well, with the assumption that nearest neighbor in a grid will also be used to display it. For instance, many images will have anti aliasing built into them so that they will look good when displayed on a "nearest neighbor grid".
Interactive applications (games), may use textures that are not meant to be displayed as is on nearest neighbor grids so are kind of an exception to that rule. They do this because as part of their execution, they do anti aliasing, bilinear texture sampling, etc, so that whatever picture they push out to the display will look good, when the display shows it as a nearest neighbor grid!
Now, getting closer to your question: would a hexagonal grid have any advantages?
I think that yes, it would!
First off, I think nearest neighbor would look better. I don't have any real proof of that sorry, but the hexagon more closely approximates a circle, and since it isn't a regular grid of data, i think your eye is getting a better distribution of data. Sorry, that is a little hand wavey.
I think the big part of why it would look better though is that linear filtering would be taking information from 6 neighbors instead of 4, and would be interpolating on 3 axis instead of 2. More information from less regularly spaced samples than a grid gives you = better resulting image.
Doing cubic interpolation would also be better than cubic interpolation on a grid, so the quality scales up as you scale up the quality of your algorithm too.
As far as whether it stores data more efficiently, the fact that it can do better filtering with less data means to me that yes, it could store data more efficiently.
And i guess lastly... maybe you could use these properties to your advantage. Maybe you could have an image format stored in a lower res hexagonal format, and then before you needed to display the image at runtime, you could use sampling algorithms to convert it back to a grid.
Maybe there'd even be a good way to do this efficiently in a pixel shader, so it would use less memory at runtime too?
It's an interesting idea (:
PS - how cool would it be to have an analog display (no individual pixels, but a continuous colored surface) that looked at the pixel data you sent not as rectangles, but instead as sample points on a continuous surface. Maybe a bit out there though....