If I download a sub-theme do I install it under the main theme's directory? For example, I found this theme, which says it requires the Nucleus Base theme.

Does that mean that I need to install it in the Nucleus Base theme directory?
Yes, you should install it under main themes directory i.e. sites/all/themes. 


Download Nucleus Base theme and put it inside sites/all/themes/ folder
Download TB Purity theme and put it inside sites/all/themes/ folder.
Go to Appearance and enable TB Purity theme. 


The concept of base theme is it provides code base to its sub-theme, so, you don't really need to enable Base theme, just keep it there for your Sub-theme to find the codes that it needs to run.