How do you find your home bed?

Using MCEdit, you can go back to your original spawn point by using "Move Spawn Point" on the hotbar and select "Goto Spawn". Then you can follow your history to try to figure out where your bed is.

If you really can't figure out, you can try the following MCEdit Filter. It will help you find your bed, but may actually take quite long (probably no less than a few minutes).

displayName = "Find beds"

inputs = (
    ("Search the whole world regardless of bounding box", True),
)

def perform(level, box, options):
    if options["Search the whole world regardless of bounding box"]:
        i = level.getAllChunkSlices()
    else:
        i = level.getChunkSlices(box)
    print "Finding beds..."
    for (chunk, slices, point) in i:
        if blockExistInChunk(chunk, 26):
            (x, z) = chunk.chunkPosition
            print "=> Bed found near x={0}, z={1}".format(x * 16 + 8, z * 16 + 8)
    print "Stopped finding beds."

def blockExistInChunk(chunk, blockId):
    for a in chunk.Blocks:
        for b in a:
            for c in b:
                if c == blockId:
                    return True
    return False

Save the file under the filters directory in MCEdit with name findbeds.py, then go to MCEdit, use Filter on the hotbar, select Find Beds and click Filter. Now watch the console (the white on black window) and it will output the approximate coordinates of where beds are found.

Sample output:

Finding beds...
=> Bed found near x=-440, z=-600
Stopped finding beds.

• Use F3 to determine your present coordinates.
• Make a chest (or two).
• Put all items in your chest.
• Kill yourself.
• Note coordinates of your bed (to avoid this in the future)
• Go to your chests.
• celebrate with fireworks....

Load your map into McEdit - this will let you fly around in the world and look for your bed. When you find it just put down your character there, load the map in regular Minecraft and you should be fine.

Press F3 after this and check the beds coordinates, write them down in case of future situations like this.