I implemented an LMS for my company and the most important things we did:
*Created an advisory committee to define all the needs and wants
*Created a small RFP regarding what we were looking for and sent to 10 potential companies to respond - it focus on the needs and included some wants and potential future needs
*Narrowed down to 4 and gave them use case studies to do a demo
*Created an evaluation tool/spreadsheet to use for the demos
*From the demos narrowed down to 2 that gave us sand boxes
*Tested the sandboxes using the use cases
I didn't do it in isolation, I ensured teams from customer service, training, marketing, Sales, the operations side, and IT were all involved.
The biggest mistakes - we didn't identify a few key needs at the time, they came up later. I don't think they would have changed our decision, and it would have made us better prepared for some things. I might have been able to get to those by walking/talking through more use case scenarios.