Per scegliere un hosting prestashop,
ci sono diversi fattori importanti che aiutano nella scelta.

PHP
Prestashop lavora tranquillamente su php 5.0 e 5.3 non lavora con il 4 e quindi nella scelta sarà meglio basarsi su queste versioni.

Linux o Windows
Linux nessun dubbio, nel caso vogliate usare windows, ci vogliono delle condizioni particolare, un ottimizzazione del sistema Apache, quindi è sconsigliato tranne che per grandi aziende che utilizzano questo sistema per altro.

MYSQL
5.0 o successive, con versioni più vecchie si possono avere delle funzionalità in meno

Attenzione nella scelta del server non scegliete server con Query limitate, prestashop è molto ingordo in chiamate al database, più in 150 solo nella home page con i moduli standard, quindi rischiate di finirle, diffidate quindi di server "tutto illimitato" dove poi il numero di query per minuto sono limitate

SPAZIO
Prestashop al contrario di quello che pensano in molti è molto limitato nel suo utilizzo dello spazio su disco, solo le immagini occupano spazio, meglio 500 mb di spazio veloce su disco che illimitati giga magari in fondo a dischi lenti e strapieni.

PERMESSI
Il tipo di ambiente varia i permessi utili e necessari per dare i permessi alle varie cartelle, ovviamente cercate di dare meno permessi possibili seguendo le istruzioni di installazione di prestashop.

Conclusione scegliete un hosting che sia proporzionale ai vostri bisogni, da qualcuno che permetta magari di crescere con il tempo, senza dover rifare installazioni e trasferimenti.
Ci sono Hosting dedicati a PrestaShop, quindi con assistenza, altri che funzionano perfettamente con PrestaShop al primo colpo e altri che funzionano solo dopo diverse modifiche. Il forum italiano di PrestaShop è importantissimo per trovare tutte queste risposte.
Il mio consiglio personale, scrivete sempre o telefonate a chi fornisce il servizio e chiedete qualche esempio di prestashop, se non sanno rispondervi o se non hanno tempo....non è l'hosting che fa per voi.