Someone told me that Islam allows marriage between first cousins (who each have a parent that are siblings). Is this correct?
Marriage between first cousins in permissible in Islam.
Marriage is only forbidden in Islam when it is between a man and a woman related to him in the ways mentioned in the following verses:
Quran 4:22-24 And do not marry those [women] whom your fathers married, except what has already occurred. Indeed, it was an immorality and hateful [to Allah ] and was evil as a way. Prohibited to you [for marriage] are your mothers, your daughters, your sisters, your father's sisters, your mother's sisters, your brother's daughters, your sister's daughters, your [milk] mothers who nursed you, your sisters through nursing, your wives' mothers, and your step-daughters under your guardianship [born] of your wives unto whom you have gone in. But if you have not gone in unto them, there is no sin upon you. And [also prohibited are] the wives of your sons who are from your [own] loins, and that you take [in marriage] two sisters simultaneously, except for what has already occurred. Indeed, Allah is ever Forgiving and Merciful. And [also prohibited to you are all] married women except those your right hands possess. [This is] the decree of Allah upon you. And lawful to you are [all others] beyond these, [provided] that you seek them [in marriage] with [gifts from] your property, desiring chastity, not unlawful sexual intercourse. So for whatever you enjoy [of marriage] from them, give them their due compensation as an obligation. And there is no blame upon you for what you mutually agree to beyond the obligation. Indeed, Allah is ever Knowing and Wise.
Additional explanations here.
First cousins do not come under this ruling since they are not mentioned.
Further we have an example from the Prophet Muhammad (p.b.u.h) himself, he married Zaynab bint Jash who was the first cousin of the Prophet, being the daughter of Umama bint Abdul-Muttalib, the sister of the Prophet's father, Abdullah bin Abdul Mutallib.