I think emr, above, makes some very good points, but I think you guys are all missing some crucial aspects of the situation.

The places where a distinctively Islamic terrorism has taken off (Algeria, Chechnya, Somalia, Afghanistan, Iraq, Syria) are all areas that have been ravaged by civil war or foreign occupation, leading to the breakdown of co-operative mechanisms in the wider society. In other words, the only move is defect. Yet at the same time, these societies (or sections of them) retain a distinctively Muslim identity and aspiration, so the natural way of forming new, co-operative institutions is to base them on that shared Muslim identity. Those participating in these movements no doubt see themselves as conducting a new Abbasid Revolution. This also draws in sympathisers from outside the country. Yet the outcome often becomes terrorism, because:

• There are non-Islamic, or non-Sunni counter-currents within that society
• Islamic regimes arouse massive hostility in the West
• Precisely because these movements arise in the context of existing civil war/violence, it leads to a Hayekian "Worst Get On Top" dynamic, where more moderate groups get forced out.

In other words, suppose you're a Sunni in Eastern Syria or Central/Northern Iraq, and you want to co-operate to protect your friends and family from, say, being kidnapped and tortured by the police. You tried voting for al-Iraqiyya, and indeed they won the election, but half their candidates got thrown out of Parliament, so they can't legally stop the state machinery from persecuting you. And those guys aren't gangsters, so they can't use extra-legal means to protect you. So maybe the co-operative move, at least in a lesser-of-two-evils sense, is to join ISIS. And hey, maybe that worked, because ISIS's success caused Maliki's government to collapse, and maybe the new government in Baghdad will govern in a non-sectarian way, at least for a while, in the same way that al-Qaeda-in-Iraq's initial successes gained concessions and allowed the 'Sunni Awakening.'

As for why these organisations are able to recruit worldwide - I don't know why you consider it so surprising that they should get "anyone at all." It's like medieval Christians signing up for the Teutonic Knights, or Georgian Hellenophiles going to fight for Greek independence. These people are ignorant and idiotic, with a notion of what they're doing that's utterly divorced from reality, but there's never been a shortage of romantic fools.

I think the linked article hits a few common themes about why this might happen:

• Sunni Islamist groups manage to convince some Sunni Kurds that the "Sunni" part overrides the "Kurd" part, at least while there's a good opportunity to gang up on a more-hated outgroup.
• Broadly, an Islamist group will claim that they represent the larger and true community of cooperators, and so defection is presented as the true cooperative move.
• The defining feature of culturally foreign recruits has been low-status, while only a weak Islamic heritage seems to be required. It's possible that literally no mainstream group wants some of these people, while a terrorist group will promise them status. Radical groups are often unwittingly assisted in this by a foreign media which dramatically exaggerates the seriousness of these groups. (This is connected to the oft-cited effect that media coverage has on encouraging school shootings).
• The community is unable or unwilling to punish defection. Bluntly, most recruits come from communities where they can expect at least ambivalence, if not some support, for actions we would describe as terrorism. Think of Saudi Arabia. Given the official ideologies, one has to resort to game theory (signaling) to explain why there aren't more recruits, and to things like Reason as a memetic immune disorder to explain who acts and who doesn't.
• The few recruits who can genuinely be described as defecting from the entire local community are more puzzling. My best guess still involves low status, the law or large numbers, and (at least sometimes) a pathological inability of the host society to respond to defectors who don't defect in culturally familiar ways, as in the recent Australian terrorist attack.

It's all about motivation. One of the biggest driver's to join a terrorist group is a sense of powerlessness over a situation or being gullible to wider teachings. I recommend reading, "Learning to Eat Soup With A Knife." Not only does it have great bits about counter-insurgency strategy it gives you a picture of the people involved.

why are they getting anyone at all?

Because people are different and in a sufficiently large population you can find outliers (don't forget people are not rational).