Migration utilities can only move standard Lotus Notes templates, (including mail). Due to the proprietary nature of Notes applications, manual analysis and then custom configuration of Sharepoint is the best you could expect. If you have custom applications, migrating them from one platform to another is the most challenging environment. If you just have mail, then the job is alot easier.
Quest and BinaryTree are leaders in the area of mail only migration. If you need to do apps as well, there is no easy solution. So, this answer is to expose the some of the real work involved in migrating applications in a high level guide.
Your best bet is to do a thorough analysis of your current environment. What typically happens is that a BP or vendor gets your mail across but not the applications, so you could be, in the worst case be stuck with a "hybrid model" where you maintain 2 sets licenses for users and servers. Most organisations have fallen into this trap. I call it a trap because the vendor probably knows this to, but if they don't tell you upfront, then they're milking the client after making some quick wins.
Here is my recommended approach, which is heavily tilted towards analysis and investigation upfront. Justification for this approach is based on seeing a few largish migrations go quite awry, the common factor is a lack of analysis up front combined with inadequate partnering from Domino specialist. The objective of this approach is to provide you with the best chance at setting realistic expectations, and completing the project in within an estimated time-frame/budget.
1/ Establish the required skill set.
Good place to start, is look at the "end-game" platform specifications, Database, server and application skills. Do you need Sharepoint only ? or Sharepoint + C# + ASP.Net. You'll need Window server engineers + Exchange + SQL Server ? Or do you also need to support MS Live Communication servers as well ?
2/ Initial resource costings.
Obtain the daily cost requirements for those resources.
3/ Estimate resource requirementsduring conversion and post-deployment (BAU).
You don't have the whole picture, but do some rough calculations in supporting the new environment after deployment. If all goes well, you can expect to taper off this resource demand within the first 6 months. Assume $5k/week/person + hardware + software licencing costs.
4/ Engage resources.
You should engage a credible Domino consultant ( or 2 for larger sites) to help you for the next phase as well as Sharepoint (SP) / MS specialists.
Current state-of-play Analysis (aka "AS-IS" Analysis)
1/ Obtain a current inventory of running applications.
Many Notes databases fall dormant in large organisations and can easily be culled from the migration once known.
2/ Identify integration points.
Focusing on current active applications, and establish all the integration points outside of the application. Over many years, Lotus Notes systems tend to be threaded into many external systems. You will most likely need to rebuild these integration services in the new platform as well. These are typically found in Script libraries and agents. You might find some nasty bits of code in Forms, but that should be the vast bulk of it.
Establish New Architecture (aka "TO-BE" State)
1/ Identify effort to re-code current applications + the integration points.
Be sure to include database designs and server requirements depending on volume. One thing I have noticed is "feature fidelity gaps" between Lotus and SP. Features you take for granted in Lotus Notes may not be available in the Microsoft stack. Ofcourse you may also get new features, but the risk here is preventing feature regression.
If features that are part of a critical application are not available natively in SP, then this presents a very high risk of cost over-run as you may have to code up the widget in C#.
I had one critical CRM application which used the Lotus Notes embedded scheduler widget to obtain available meeting times of users. AFAIK this widget is not available in the MS solution stack. Perhaps there is a 3rd party solution, or has since been implemented natively. So you need to identify them with the SP and Domino specialists working together. I have a final hit list below of things to watch out for, (see "Navigating the document minefield" below)
2/ Eliminate "feature fidelity gaps".
Now you should have your inventory of applications to migrate. Any significant "feature fidelity gaps" risks identified should be investigated with a pilot to know that it can be resolved. Or negotiate with system owners to work around features not available in the new platform. This is your go/no-go point.
3/ Detailed project plan.
Create your project plan at this point. It should have 2 distinct parts email migration and application migration. Typically the CIO will mandate mail to go first, I think this is potentially a big mistake because because the applications take easily 12-18 months on average to move assuming no major budgetary constraints, otherwise it's anyone's guess. An ill-informed CIO can leave a company crippled in a hybrid model with skyrocketing resourcing costs if they focus on the quick win. Be it because of pressure from the board, or ego.
One approach to is to migrate native Lotus Notes applications to the web first, and thus un-shackle you from the Notes client, (beware of offline access requirements here, see below). A recent Domino based product, (the evolution transformer), that claims 100% fidelity of migrating your applications may be worth considering this as a transitional step. to reduce ongoing licencing costs if you have a prolonged application migration.
But I would recommend structuring your migration plan in phases. Phase 1 should be small easy apps and some mail. This is like a pilot, you will learn alot from this phase, so keep it small and complexity as low as possible. Phase 2 and so on are as you see fit, scaling up as required depending on budget, resources, complexity.
4/ Communication plan.
Think about how you're gonna get this change through to users. Afterall, some will think, "we are going from an email system to another email system". Or they'll be resistant to losing applications they might be comfortable with. Ideally you'll want to bring them willingly. So, plan to identify and garner support from key users who have influence with others.
If you've done all the analysis work and planning, then this step should be un-eventful. What is important is communication with the business and make sure your users are onboard and informed. Make sure you have a pre-production environment to kick around because you'll want to know problems before real users get them. Get "user champions" who can give it to you straight and don't just flail their arms about when something goes wrong.
Navigating the document minefield
Application based Document links : If you have document links that are embedded in rich text fields throughout applications, how will you convert those links into the "new world"
Email document links : Applications tend to send links in emails to documents. You will need to consider how to convert that for sharepoint.
Long term storage / Legal compliance: Sometimes legal compliance requires that you keep servers and databases available in "original format". Financial organisations tend to have this compliance requirement.
Local Replicas and offline access: If users have local replicas running on their laptops or home pc's they will lose this in the migration.