Latin Square : an NxN? square grid of cells, where each row and each column contain the digits 1-N exactly once.
Sudoku : a sub-type of Latin Square, in which a third group of constraint has been added - regions. There are N regions in the grid, each containing N cells, and usually (for grids when N is a square number) each region is a square box (though it doesn't have to be). For N=9, there is a convention of numbering these boxes across and then down: 123 456 789
A horizontal set of boxes is sometimes called a "band", while a vertical set is sometimes called a "stack".
There are many variants that add additional restrictions, or which play with the above (eg using a different set of 9 numbers) that are also usually included as being Sudoku.
People on ToothyWiki known to solve these types of puzzle from time to time include: