No matter which way you go about it, your looking at a minimum of 2 changes. If you get an EC service from Aberdeen, then I suggest changing at York onto an XC service (get the XC service that goes via Doncaster as there will be more seats available) to Sheffield, then the Northern or EMT service to Nottingham from there.
Alternatively, if you catch a Scotrail service from Aberdeen, then change at Edinburgh. From there you have a choice, follow the advice as above from York, or change at either York or Newark plus Grantham (the East Coast website is offering routes via Grantham).
PS. I've just checked again, and via Derby is being offered as a valid route as well, so from York, you can catch the XC service to Derby for a service onto Nottingham from there.