I always rename a class from a project, either using Save As... or Move on Disk.... In either case I also specify a new destination folder with the new name. Methods associated with the class I then move in the project files view. Yes, as mentioned above, it is necessary to delete the old, now-empty folders outside LabVIEW (from a file explorer application), unfortunately. (NI changed this for LabVIEW 2010: see "Restore 'Delete from Disk' in project Files view" topic in the Ideas forum for more details.)
With TortoiseSVN (i.e., outside LabVIEW) it is possible to specify that one file is the rename of another, so that the new file will keep the old file's history. I recently joined a new organization that uses Git, and I haven't investigated how to do that with Git yet.
I use the LabVIEW IDE's search and replace functionality to update the icon names on the object control and indicator names in the class methods. This is fairly straightforward, since it is pretty easy to select the VIs in the class for search scope.
The process works well enough for me with too much trouble (although I don't always end up being able to link the new file to the old history), but clearly this requires more effort than it should. (I'm reasonably happy working with TortoiseSVN outside the LabVIEW IDE, but fully capable integration with source code control from the IDE would simplify these steps and reduce errors.)
A few years ago someone posted a tool on LAVA designed to facilitate renaming of classes. I haven't tried it myself.
This discussion points out areas where the project (failure to delete folders from disk) and version control integration (inability to rename files effectively--which requires the ability to delete folders) are incomplete in the LabVIEW IDE. It seems clear to me that a complete solution integrated with the IDE (clarification, a complete integration with external source code providers) would be quite beneficial. (OK, the fact that some people are seriously suggesting not to rename classes is a pretty big red flag here.)
When it comes to renaming classes used in multiple projects, there are fundamental limitations, since an unopened project does not "know" what happened to a class also used in another project. If one can reasonably create a project with all callers, that works, but that isn't always practical. Putting classes in project libraries helps (the library, shared between projects, tracks changes internal to it, instead of multiple projects), where this is appropriate.