How to minimize the gates in implementation?
There are a few formal methods of approaching this problem and are well documented. One of them is the K-Map or the Karnaugh Maps, and the other is the Quine-McCluskey algorithm.
There was another method which was quite tedious which I had learnt, unfortunately I don't remember it now. 

But these two methods should serve your needs most of the time (not all). Quine-McCluskey method offers better results but is longer and iterative, but scalable. K-Map is a graphical method which is quite simple but gets tedious as the number of inputs increase.

But in all cases, they are better than plain guessing, the latter having a certain edge.

Edit:
After having a minimal expression, it is usually through algebra and practice that you obtain NAND and NOR implementations. Now I've not looked beyond my text books, and hence am not aware if there are any formal procedures.