I recently lost quite a bit of data due to a power outage, and tried recovering it by grepping through my swap partition. I found bits and pieces, but every line of data I found would be preceded and followed by garbage. How does the swap partition store data, and how could I go about creating a program to reconstruct the bits and pieces of info in swap? And, more importantly, how much work would it be?

A swap partition contains essentially fixed size blocks of data (4KB) corresponding to portions of memory contents the system decided to place temporarily there because RAM was needed for another use.
Depending on your RAM size and your applications demand, your swap space may be never, moderately or heavily used, with the performance of your system degrading "exponentially".
The problem in what you are trying to achieve is that your are looking for "lines of data" on a partition containing pages that it is impossible to order or even connect to a specific process, because all this indexing was lost when to O/S stopped.

The truth too is that a lot of data was definitely lost anyway because it was only present in RAM. The data available in the swap area is randomly located and there is no way to know if the pages are valid, or just "ghosts" of previous versions of data obsoleted by an update.
Data present in the swap is also exactly laid out under the form the application itself used in memory, which is usually different from what you expect it to be (a file saved on disk), explaining probably most of the garbage surrounding what you already found.

Sorry to be so un-optimistic, but I think trying to build something from a swap is a waste of energy.

Not sure about how you "grep" in the swap, but probably the best command to use here is "strings", which is able to extract anything that looks like a string from garbage.

To grep through the swap I used dd to create an exact image of my swap partition, and then used grep to search for keywords I knew my data contained within the swap file. I found several lines from my data, but I guess it is lost. Strings still turns up lots of rubbish, and if there is no way to tell what data belongs with what, I would basically have to rewrite a swap filesystem, wouldn't I?

this might help: vim tries to recover data from swap, maybe you should check that out. i realize vim source is huge, but maybe you could google to get some idea how it does it, or post on a vim mailing list or something.

vim creates little files called swap files while it's editing, e.g. .foo.txt.swp when you edit foo.txt. This is what it restores from. This is unrelated to your swap partition, unfortunately.

The swap partition doesn't contains anything like a file-system, so it is pointless to write a "swap filesystem".
Swap only purpose is to allow more programs to run concurrently than the actual physical memory would support.
Nothing to help you restoring lost data, unless you are very lucky.

I suggested to use the command "strings", did you tried it ?

You do not tell us what kind of data and what program was used to manage it too.

--edit--
Sorry, you did try "strings", I missed it in your answer

To summarize,

The fundamental problems here are that:

The order and encoding of your data within swap space is dependent on the application you were using to edit it, as well as on the whims of the kernel

and

Your data may not have *ever* made it to swap in the first place, or only parts of your data may have made it to swap.

So, the data may not be recoverable at all, and, if it is, there's no generic way of doing it.