The first step is to ensure that the chairman and Head of IT are the project source and give to the project manager all the cards to implement the various processes attached to ITIL.
Obviously all head of department must be stakeholders in this project.
Stakeholders : Chairman, Head of IT, Head of IT operation, Head of IT infrastructure, Head of IT security...., IT service desk, Head of business department.
Start the project by a mandatory conference for all users in order to inform what is ITIL and why the company needs to implement it. Include link to ITIL website and send a communication by mail or through intranet.
Create a project charter to sell ITIL and CMDB for your presentation.