The first question to ask yourself is, am I ready to apply to PhD programs or should I get a terminal MA first?

• Apply to PhD programs if and only if you know your field specialty, have a general idea of the direction your dissertation will go (more specific than, say, "medieval women...Ireland is cool"), have a working command of your research languages, and know how to formulate a historical research question and how to answer it

• Apply to MA programs if the above conditions are true, as backup; but also if they're not.

The biggest thing I see in your post is that you're not quite sure yet what you want to do. You really need to be able to hit the ground running in PhD programs. This was less true even 3 years ago, but more and more unis are trying to push grad students out the door as fast as possible ($$$...don't wanna subsidize that health insurance). In your application, you will need to be able to show you are committed to a subfield and a topic within that subfield, even if your question is going to morph a little right through your actual diss writing process. ;)

There's nothing wrong with a terminal MA first. For medieval, at least, it's quite common thanks to languages and the extra skills required (paleography in particular).

So how do you find a program?

For MAs, the most important thing is funding. If you can find a school that has outright fellowships for master's students, that's a fantastic deal. Otherwise, browse departments at major universities to see what they say about TA opportunities for master's students. One thing you might consider is looking for schools that have ONLY a master's program; no PhD. In schools with both, sometimes master's students get overlooked by the faculty in favor of the PhD students. (Also, note that while many PhD programs grant a master's "along the way," they do not have a formal MA-only program.)

For a PhD program, it's as much about the professor as the department. Who is going to be your dissertation advisor? That's the real question you're asking yourself. Look at the books you cite the most, the scholars currently working in academia who do the type of research you want to do (methodology wise) in the general vicinity of what you want to do (e.g. medieval cultural history). Find out where they work. Is it a uni with a PhD program? What sense of that program do you get?

That's how I made my list. I'm working with exactly the advisor I should be. :)

Since you asked about doing graduate work in Europe, and TCD in particular, with which I'm especially familiar, I'll chip in here.

Firstly, if you want to do a PhD in Europe, you're going to need to do a 1-year terminal master's degree first (usually an MA, but some places call it an MPhil or similar). You won't be accepted on a PhD program without one. It's highly unlikely to be funded, as TAing and other scholarship funding tends to be reserved for PhD students. You'll need to budget a minimum of probably $15,000 for tuition, plus living expenses. The good news is that you don't need to be too specialised going into these programs and any language skills you have will be a bonus. The bad news is that you will, at the very least, need to pick a period you want to focus on - either the modern (19th-20th), early modern (16th-18th) or medieval. You'll improve you language and writing skills during the course of your masters, become more familiar with your subject and be in a better position to apply for PhDs (which do offer the possibility of funding). Remember, a PhD in Europe is very different to a North American PhD: there's no coursework, it's independent research and dissertating from day 1.

As for choice of universities, TCD is a great place to come if you want to study Irish history. It's already in Ireland, so you're close to lots of resources, plus it's got one of the highest concentrations (if not the highest) of specialists in Irish history in the world. TCD has well regarded MPhil programs in medieval, early-modern and modern history, with a heavy emphasis on Irish history. I can offer even more info on medieval history, if you're interested in Ireland. The TCD MPhil will give you the chance to improve your Latin and to learn Old Irish (vital if you're going to study early medieval Irish history), as well as develop palaeography skills using its pretty bitchin' Jedi manuscript collection. There are full faculty members specialising in early, central and late medieval Irish history, as well as plenty of distinguished ermeriti who show up frequently. You won't be lonely as an American either: about half the MPhils each year are usually from the States or Canada, and several of the PhD students are too.

Outside of Dublin, there are plenty of options too to study medieval Irish history, although they're more dispersed, so you'll need to have a better idea of your interests in order to match with the best one. If languages, literature and early Irish history is where you're heading, check out Cambridge's ASNC department too, which have excellent interdisciplinary early medieval insular scholars. Like others have said though, narrowing down your interests and finding the appropriate scholars to work with should be your main aim at the moment.