a procedure can be defined and used in a script. If you are familiar with other languages it's basically a function. It takes parametres (but doesnt have to) and returns a value but again doesnt have to.
A script is a bunch of procedures and other code written together to do a specific task. It can have procedures etc.
An expression is typically done on one or more "channels" in maya. E.g. pCube1.tx += 1; in the tx channel will move the cube on a frame by frame basis along the x axis.
Hope that helps a bit
Technical Director - Framestore
Currently working on: Your Highness