Se si parla di logo, si parla di grafica vettoriale.
Le dimensioni quindi sono irrilevanti nel senso che, lavorando in vettoriale, il logo può assumere tutte le dimensioni che vuoi (da 1cm x 1cm fino ad una dimensione relativamente infinita). Di programmi per lavorare in vettoriale ce ne sono tanti, Corel Draw è uno di questi, poi ci sono Adobe Illustrator e Macromedia Freehand che sono i più diffusi.
Photoshop è un tantino differente perchè è specializzato nella grafica raster, però lavora anche in vettoriale, sicuramente senza la comodità che potrebbero avere i programmi elencati prima.
Ovviamente per creare un logo ci vuole creatività, oltre alle cose che ha elencato prima whitefox
1)il nome dell'azienda/impresa/etc.
2)l'idea che ha il cliente (colori, stile etc.)
3)il target dell'azienda/impresa/etc. per cui stai facendo un logo
Per il resto ti posto il link di un tutorial molto utile per la creazione dei loghi, è al sito di Memole
http://www.ideespettinate.it/write/logo.php


Ciao