What is the relationship between being normal and being regular? On a scheme, being normal means that each stalk of the structure sheaf is a integrally closed domain.
Being regular means that each stalk of the structure sheaf is a regular local ring.
As for a local ring, being regular or being integrally closed does not imply another.
What is their connection with each other and classical/usual intuition of being smooth(being regular on stalk of each closed points)?
Moreover, is there a smooth/regular variety which is not normal?
 A: You seem a bit confused.  A regular* local ring is a UFD hence integrally closed.  In other words, regular implies normal.  See for instance
http://www.math.iitb.ac.in/atm/caag1/jayanthan.pdf
for a relatively elementary algebraic treatment.  
*: I had previously included Noetherian here, but after checking on this I see I was being overly careful: it is part of the definition of a regular local ring that it be Noetherian.
A: Dear 7-adic, yes there is an implication between the two notions.
For a local ring, regular implies normal. Actually Auslander and Buchsbaum proved in 1959 that a regular local ring is a UFD and it is an easy result that a UFD (local or not) is integrally closed. Serre then gave a completely different proof. He proved that regular is equivalent to having finite global (=homological) dimension . This finiteness means that any module over the ring has a finite projective resolution. I have heard it claimed that this was the beginning of the acknowledgment of the importance of homological algebra in commutative algebra.
An example.The cone $z^2=xy$ in affine 3-space (over a field, say) is normal but not regular: its very equation suggests that we don't have the UFD property and this intuition can be converted into a rigorous proof. 
Normality is a weak form of regularity. The two concepts coincide in dimension one but not in higher dimensions: the quadratic cone above shows this in dimension two. 
Finally, smoothness is even stronger: it is a relative concept meaning regular and remaining regular after base change.
