Nucleophilicity is a kinetic descriptor. It describes how quickly the species can form a new bond to an electrophile. There are two main things that make molecule nucleophilic: polarizability and basicity. For the purposes of predicting reactivity, a base strong enough to do an E2 reaction generally has a conjugate acid with a pKa of roughly 16 or larger. In other words, hydroxide/alkoxides or a stronger base.
I break nucleophiles up into 4 electronic classes. I'm ignoring steric effects here because I'm already typing a lot...
Polarizable nucleophiles: Larger elements are more polarizable. By larger, people generally mean below the second row in the periodic table. Polarizable elements are "soft" and their electrons are easily pulled toward partial positive charges in electrophiles. This makes them better nucleophiles. Examples of polarizable nucleophiles are: Iodide, bromide and Sulfides (RS minus). These polarizable nucleophiles are also by definition weaker bases than similar non-polarizable nucleophiles because the larger elements form weaker bonds to hydrogen than the smaller elements. So there's no risk of E2 reaction.
Moderately basic non polarizable nucleophiles: There are also some of examples of what I call "medium" base nucleophiles containing non polarizable nucleophilic atoms. Examples of these are carboxylates, cyanide and phenoxide. These guys have conugate acids with pKa ranges of around 4-10. They are not particularly great bases, but they are sufficiently basic that they can do fairly fast Sn2 reactions despite their lack of polarizability. They work well for primary and secondary substrates, because elimination does still does not compete well.
Strongly basic non polarizable nucleophiles: Alkoxides, hydroxides, R2N-, R3C-, etc. These have conjugate acids with pKa's of 16 or greater. These ones work mainly for primary halides due to competition from elimination with secondary halides. And things much stronger than acetylide (conjugate acid pKa=25) don't even work very well for primary substrates, possibly due to competition from E2 elimination although I'm not 100% sure why.
Very weakly basic, non polarizable nucleophiles: The include water, alcohols, and the conjugate bases of oxoacids such as HSO4-. These guys don't work very well for any kind of Sn2 or E2 reaction because they lack both properties that make up a good nulcleophile, one of which is basicity.