Culture - waterfall culture is difficult to change... switching to agile is a fairly fundamental mind-shift. You'll get lots of worried looks from accountants who cant understand how you can cost a project without first fully specifying the deliverables
Education and know-how - you can't just pick up an agile book, read it, and then make your org agile... you need a planned approach to introducing agile and you will need support from experts who've been there and done it. If you try to shoehorn agile in, you may go completely off the rails and lose the faith of the senior management team. I'd suggest small, achievable pilot projects to demonstrate proof of concept and build steadily from there.
I think effective introduction is much easier for a small company / org. If you work in a large organisation, you'll probably want to trial it with relevant small teams in the org first.
Customer / stakeholder culture. You cant work in an agile way if your customer isn't up for it. Agile is all about very tight partnership working with the customer throughout the project. If the customer doesnt have the time or inclination to give the project the time it needs, you will be flying blind - developing your product without the necessary feedback.
Old school procurement processes - in a lot of large organisations the procurement function doesn't understand agile and will probably try to block it. I've worked with large organisations to procure software where I get given a fixed budget and am forced to specify all of my requirements (functional, non-functional, commercial etc) up front in an invitation to tender document. I then receive detailed bids which explain exactly how each supplier will fulfill my requirements. The whole selection process is engineered around the principle of understanding which supplier best meets my stated functional needs. The waterfall approach is ingrained in the procurement process.
Get help from a seasoned expert - someone who has a proven track record of introducing agile into agile-phobic organisations. They know the pitfalls and can act as a coach/mentor.
Start small and grow organically - you cannot change an organisations mindset overnight. Demonstrate small but significant early successes. Extoll the virtues of agile to management and back this up with evidence.
Training - working in an agile way needs know-how. Make sure your staff receive relevant training in agile approaches - e.g. DSDM Atern, Scrum etc.
Use the right tools - certain development frameworks are inherently more agile than others. Make sure you are using tools that enable an agile approach. For example ruby on rails embeds much of the agile ethos - e.g. Dont Repeat Yourself (you only need to write code once in one place)
Understand that agile is not suitable for every aspect of every project - for example the production of a nuclear power station... you couldn't deliver early and get the core reactor up and running before implementing all of the fail-over and safety systems!
Deliver business value quickly - why wait for the entire waterfall cycle to complete before delivering business benefit?
Flexibility and adaptability - neither you nor the customer knows exactly what is needed to solve a business problem until you've gotten stuck into a project. Learn as you go and adapt the product accordingly