A NonEuclidean Geometry is any geometry that does not follow Euclid's 5 axioms of the intuitive geometry we naively perceive. Historically, the first non-Euclidean geometries arose from considering violation of the fifth axiom, as discussed below, but there are many other types of non-Euclidean geometries as well.
Way back when, EuclidOfAlexandria's Elements gave a bunch of axioms that were supposed to define the geometry of the plane. One of those axioms, the so-called ParallelLinesPostulate, was conspicuously less natural and inevitable (and also more complicated) than the others, so of course mathematicians wondered whether they could do without it. Pretty much everyone expected to be able to do without it.
It turns out, however, that removing the ParallelLinesPostulate from the axioms really does make a difference: there are spaces that satisfy all the other axioms, but not the ParallelLinesPostulate.
Here's one of them. Take a circle; everything lives inside that circle. (Call it C.) A "straight line" is a circular arc that meets C at right angles. A "point" is, er, a point. The angle between two "lines" that meet is the angle between their tangents at the point of intersection. Distances are calculated by a slightly complicated formula that I'm not going to tell you. It turns out that this satisfies all Euclid's axioms, and also all the other ones that he would have put in if he'd realized that they were needed, apart from the ParallelLinesPostulate. It's called the HyperbolicPlane?. (There are, by the way, plenty of other - equivalent - ways to construct what is basically the same space.)
Here's another NonEuclidean space. Take the surface of a sphere. A "straight line" is a great circle (i.e., a circle on the sphere whose centre is the centre of the sphere). A "point" is a pair of antipodal points. Angles are again defined by taking tangents; distances are again defined by a formula I'm not going to tell you. This is the ProjectivePlane?, and it too satisfies all the axioms apart from the ParallelLinesPostulate.
It turns out that there are lots and lots of NonEuclidean "planes". And, unsurprisingly, something similar happens in higher dimensions. This is generally not expressed in terms of satisfying all but one of a bunch of axioms; rather, there's a general concept of RiemannianManifold? (meaning "thing where you can do geometry, with distances and angles and stuff, in which very small areas always look - topologically - like EuclideanSpace?") and most Riemannian manifolds are NonEuclidean.
The specific examples generalize: in any number of dimensions there's a HyperbolicSpace? and a ProjectiveSpace? - but there are many, many more (mostly less "regular") NonEuclidean spaces than those.
Our own "familiar" universe is NonEuclidean, according to GeneralRelativity.
Ahem. "NonRiemannian?." Don't worry your pretty head about that one. -- PhlIp
Nope. It's NonEuclidean and Riemannian, not NonRiemannian?.
"I never forget the day I was first given an original paper to write. It was on analytic and algebraic topology of locally Euclidean metrization of infinitely differentiable Riemannian manifold. Bozhe moi! This I know from nothing!" -- "Lobachevski" (TomLehrer)
Sounds like a candidate for OmnigonInternational ;-)