These recommendations are premised on the thought that one needs a good education in philosophy in order to be able to do good philosophical scholarship related to Nietzsche.
Among the very top PhD programs in the Anglophone world, there are four viable choices for a student wanting to work on Nietzsche: New York University (with John Richardson and Tamsin Shaw), Oxford University (with Daniel Came and Peter Kail), Princeton University (with Alexander Nehamas) and Stanford University (with Lanier Anderson and Nadeem Hussain). I am not sure how hospitable these places are for students primarily interested in Nietzsche, given the dominant interests of the faculty and most of the students, but they deserve serious attention from prospective students: you will get an excellent philosophical education and you have good philosophers who can serve as advisors with respect to Nietzsche work. Each of these faculties also includes philosophers interested in other aspects of Kant and post-Kantian Continental philosophy, including Beatrice Longuenesse at NYU, Alan Patten in Politics at Princeton, Michael Friedman at Stanford, and Stephen Mulhall at Oxford.
Among strong, but not very top, PhD programs there are several additional choices I would recommend: Birkbeck College and University College in the University of London system; Brown University; University of California, Riverside; University of Chicago; and University of Warwick.
In terms of sheer numbers, and diversity of approaches to Nietzsche, Chicago has the most faculty to offer across various units, and for a student also interested in ancient philosophy and/or wanting wide coverage of 19th- and 20th-century European philosophy, Chicago has a great deal to offer. (Faculty interested in Nietzsche, and supervising students, include James Conant, Michael Forster, Robert Gooding-Williams, Brian Leiter, Martha Nussbaum, Robert Pippin, and David Wellbery.) Brown is stronger in most contemporary areas of philosophy (with a particularly good group in moral and political philosophy) than Chicago, but has less depth and breadth in post-Kantian philosophy of the 19th- and 20th-centuries. (The key faculty are Bernard Reginster and Charles Larmore; they will be joined this year by Paul Guyer, making Brown a major destination for Kant students, and also adding coverage to aspects of German Idealism.) University of California, Riverside also has a strong group in post-Kantian European philosophy, including Maudemarie Clark (a leading Nietzsche scholar, of course), Pierre Keller, Georgia Warnke, and Mark Wrathall, and UCR also offers solid, sometimes outstanding, coverage, across a range of contemporary areas of philosophical research. University of Warwick has been a major up-and-coming department in the U.K. over the last decade, and is now solidly among the top ten U.K. programs. Keith Ansell-Pearson and Peter Poellner are the two main faculty interested in Nietzsche (their approaches are quite different, Poellner's being more likely to appeal to students with philosophy backgrounds), but other faculty do important work in Kant and post-Kantian philosophy (Quassim Cassam, Stephen Houlgate, A.D. Smith).
Birkbeck has my good friend Ken Gemes, a very talented philosopher who has supervised a number of students working on Nietzsche, and the Nietzsche scholar Simon May is also around and available to students, though not teaching regularly. Birkbeck's main strengths, however, tend to be in contemporary areas of Anglophone philosophy--like philosophy of language, mind and action--so as with Princeton et al., students should investigate what it is like for students. (Gemes is also now only half-time at Birkbeck.) At UCL, Sebastian Gardner, Mark Kalderon, and Thomas Stern are all interested in Nietzsche, and Garder and Stern are currently writing on him.
A few other programs worth considering:
Boston University, a top 50 department which also has strong coverage of 19th-century philosophy, has Paul Katsafanas (whose Nietzsche work is known to readers of this blog), who will surely get tenure before long. BU thus deserves to be on the map for students thinking about graduate work on Nietzsche. University of Southampton, though not a very good department overall, is attractive for a student interested in Nietzsche, with Christopher Janaway, David Owen, and Aaron Ridley. Raymond Geuss at Cambridge University has worked with some students interested in Nietzsche, but he will be coming up against mandatory retirement shortly, and has been dissuading students from coming to the philosophy faculty, alas. Among the top M.A. programs, the hands-down best choice is Georgia State University, which includes two Nietzsche specialists (my former student Jessica Berry, as well as Gregory Moore), and a specialist in German Idealism (Sebastian Rand).
Things are looking up on the European Continent for philosophically-minded Nietzsche scholars. I have been impressed by Joao Constancio's group at the New University of Lisbon, and by other younger scholars I have met (either in print or in person!) in recent years. But I am not well-informed enough about the overall programs there to offer meaningful guidance to my non-Anglophone readers.