What is the most effecient way to do this? Is there a way to store all the sprites coordinates in some data-structure that keeps track of all collision?
I find comparing each sprite with all sprites is a bad idea.
Thre have been long discussions on this already. Try searching the boards.
There are many tutorials in the web.
Search here, or gamedev.net or gamasutra.com.
The question is, how precise you need your collision.
The main way would be to do quick and easy tests first and to exact tests if the easy test shows a collision.
Easy tests are bounding box/rect or bounding sircle.
Bounding box/rect means you get a rect around your sprite, and another rect around the other sprite, and then you just check if they intersect.
Bounding circle means you have a middle of each sprite and a radius of its size. Then the distance between two middles must be greater than the sum of their radi, then they dont collide.
This tests are mathematically easy and fast, but not precise. But they will help to eliminate a hell lot of tests for objects that dont collide. All objects that DO collide run a second more precise test to test if they really do collode.
In many cases, the easy tests are all you need. One hint is to use a bounding circle and the set the radius to 80% of the real max radius. This 80% will give you the core area of your sprite while it leaves out some edges. While this isnt precise, its precise enough in most cases.
You can do a bounding polygon, which is also mathematically far faster than a pixel per pixel test.
When doing a pixel per pixel test, you should consider only to test border pixels, not the inside of the sprite. when the sprites intersect, their border should intersect on some point.
As I said, search the web. This topic is widely covered.
-JAW
I see you’re also asking whether or not it is smart to test each and every sprite against each and every other sprite, because that has a BigO of n^2, which is pretty slow. Faster methods largely depend on what exactly your game is like. If you have a 2D grid-type game, you can of course simply check array locations, which is very efficient but not logical for most modern games.
Here is what I use and recommend for a top-down 2D grid-style game. I have no idea if it is the best way or not, I usually come up with my own ways of doing things.
Have a 2D array to represent all sprites that might need collision testing. Say you have a 30x30 grid to represent you entire level, each grid space being 50 pixels wide/tall. Your collision array should represent each block and the blocks surrounding it, so a 10x10 grid with each grid space being 150 pixels wide/tall. Then, every timestep, adjust every collidable sprite to the correct position within the grid. Say it is currently at 350,100 on the screen. That means it should be moved to [1][0] in the grid, because every 150 pixels it should move to different location. Then when calculating collision you only check within each sprite’s collision grid space. The efficiency of doing it this way is BigO n, significantly faster than BigO n^2, although I doubt the fastest possible.
Understand what I mean?
I think you expressed yourself clearly, Demonpants. Each tile stores a list of units presently inside it. However, assuming that sprites may at one point overlap several tiles in your collision grid, you will have to traverse all 9 tiles surrounding any unit and compare with all other units registered in those tiles. Also the size of a sprite must not be greater than half the size of a tile, which poses a hard-to-remember limit on unit size (remember to throw exceptions if too large units are made 
).
In our current project we use a slightly diffferent approach. A sprite may be registered in any number of tiles (typically 1-4, but for large sprites the number could be arbitrarily large), and it checks for collision with every other sprite registered in any of those tiles. This adds some overhead here while removing overhead there. However it allows any sprite size, and on a side note it also allows us to easily implement a similar system for checking whether terrain needs to be re-rendered (which it doesn’t, unless units are near). It would be bad to have other sprite size restrictions due to the different terrain tile size.
Well, in order to eliminate overlap problems and large sprite issues you have to do some extra fringe cases I did not mention in mine, that I do have in my code. I was trying to have him understand the general gist of it.
Your method seems interesting. Does it basically do the same thing only it checks across multiple tiles if need be?