Cleaning of a blade can be done with a fresh lemon or lime. It takes some time. With a rusty blade i brush the blade with the fresh lemon or lime. Put the piece of lemon on the rusty spot and pack the whole thing in plastic and let it rest for some time. The unpack it and scrub again with the lemon until the rust is gone. Staining is done with warangan like Detlef said. Search for it on this forum.
The hilts you found are indeed a form of madura hilts.
This link shows other maduran ukirans.
http://www.vikingsword.com/vb/showth...ghlight=madura