I am currently working in US in H1B status. I plan to go to Nepal in a month or two. I know that I need to have my visa stamped before returning to US. But I am not sure if I need to get a certificate or permit from the Department of Foreign Employment too. If anyone has experience or idea about this please share it. I would really appreciate your help.
Also if a permit from DoFE is mandatory for H1 visa holders, what docements are required for the process?

Yes, you do need a sticker from Dept of Foreign Employment. Not sure, but heard that some people were sent back when they did not have the sticker at the airport. I got it when i went back last year. But, sure they do check at the airport. So, just get it to be safe.
The documents you need are:
Filled up form which you get in same place.
Passport with H1B visa Stamp.
Letter when you were hired stating your salary.
You need to take insurance as well ( there are several insurance company near to Dept of F. Employment)

efg is correct.

YES, You have to get the work permit from the department of foreign employment. This has to be done once you get your visa stamped.
I was in Nepal just couple of months ago. Alike you, I made sure that I had to make work permit from DoFE, or I would had problems at the TIA while leaving for US. The most important documents you need are passport with visa, couple of your photo (more count is always good), your job offer letter stating your salary and position. However, I took all the documents that I took for visa interview just to be on the safe side. If you have been in US for a while or have not been through the government office process in Nepal, all these process will make you irritating.
If you know anybody from the manpower company in ktm, ask help from them. They know what needs to be done and will be really helpful. Or you can pay some fee to an agent who you can probably find at the DoFE office location.You need insurance also. but there are several offices of insurance companies at the location of DoFE. DoFE is location at Tinkune (ali bhitra-bhitra baato cha jasto lageko thiyo). Get the work permit first and then work for insurance. Total cost for work permit and insurance might be around NRs. 3000 but i think insurance costs might dependent on how long your visa is.
Depending on my experience, I would recommend you to get the help from a manpoweer agent. You can pay some fee (don't know exactly how much) if you don't have friends or relative working for manpower agent. They will definitely save your time. Time spent in Nepal in this people like us is very important.
Goodluck