limit how many things move in your layers.
also try to keep the colors down when possible.
I try to get all layers used done first then build the animation.
Flatten any filters like drop shadows or glows into the layer before animation.
People will tell you to flatten the entire image for each frame, I've noticed that eats up KB's a lot of times especially on very colorful images. I just flatten what wont move, and use layers turned off and on for each frame that I want to animate. and move that layer around when ever possible.
Try to avoid large pictures where most of it isn't even in frame. Unless you're using it for your background. Even then it's going to take up KB's.
BUT its basically trial and error for me. I don't have a real 'secret'... but I've noticed the above holds true in being able to successfully animate under 512kb.
my latest gif (for a future contest) was 46 frames and 464kb with no loss in detail. Used a static background with the subject moving around the frame.
my last gif (already past) the Journey (the fish one)
http://photoshopcontest.com/view-entry/172956/the-journey-gif.html
that was 26 frames and was exactly 512kb with lots of loss. I had a lot of layers and a huge background that moved from left to right through most of those 26 frames though.
Secret Squirrel was the same
http://photoshopcontest.com/view-entry/164752/secretsquirrelgif-sc.html
came in at 22 frames and roughly 436kb
I've left the PSD in both authors notes if you're interested.