How desperate is too desperate when it comes to contacting supervisor? I am trying to create a solid basis for applying for a highly competitive PhD position in the field of CS.
I am now getting as much research experience as I can by doing internships in academia and companies, I also do a lot of networking and get myself introduced to people in the field. I try to keep in touch with my former supervisor (MSc). For example, now as a result of my recent internship I am working on a paper, and he agreed to co-author it. Also, I am starting to work on another project on my topic, and I am planning to inform him as well. I regularly (once in a couple of months) write him telling him what I am doing and asking him whether my new step (application for a new internship etc.) is advisable.

He is always nice but I am wondering whether it is actually good practice to keep bothering your supervisor after you graduate from an MSc, even if potentially you want to apply for a PhD after his supervision. Doesn't it seem to desperate or pushy?
Keeping in touch with a former supervisor is hardly a negative, particularly since you are collaborating with him on a paper. 

At a rate of an email every couple of months, this frequency of your communications doesn't make you appear desperate or pushy. Whether these qualities come across in what you write to your former supervisor, or how you express yourself, is impossible to determine. 

Maintaining good links with your former supervisors and collaborators is excellent practice, so long as you remain pleasant, polite, and on topic. 

Deciding what the best thing to do regarding internships and applications is always tricky. Gaining the advice of your past supervisors is a good idea, and most supervisors would see it as part of their ongoing pastoral care to provide their opinion on your career progress. Don't, however, expect anyone to make a decision for you.