Are the iNotes servers new or existing servers?
Yes, I would cluster, more for backup/dat loss prevention than iNotes failover, because last i knew, iNotes/ iNotes Redirect (IWAREDIR.NTF) are not cluster aware.
I'd first setup/configure/test the iNotes servers. Once you're happy that iNotes is working, you can use the Admin client/AdminP process to move users to the iNotes server(s) where you'd like them.
As you're moving users, you can run decommission reports on the servers that you'd like to remove (again using Admin client) to see what other functions might be affected by the server removal.
Once all the users/functions are moved off each server, you can remove the server (again using adminP).
Keep an eye on the Administration Requests database throughout the process.
One other note - you might want to verify the ACL of user mail files during the move process, especially if users are not using their Notes clients during the process. I ran into issues with some user ACLs not being updated.