Bufff, a ver, para aprender php necesitas unos conocimientos básicos de programación, ya que se asimila bastante a C, pero no es muy complicado.
1. Que software necesito? -> Tanto en windows como en linux necesitas, el propio php, y un programa de servidor web, el mejor, sin duda, Apache. En windows tienes programas que te instalan esos 2 programas, y mas, como MySQl (importante si quieres usar php con bases de datos), Python, phpMyAdmin, etc... En linux no conozco un programa que te instale todo, asi que tendrias que hacerlo por separado, pero no tiene ninguna complicación.
2. Con mi modem 56k puedo hacerla? -> Siempre que no quieres tenerla en tu propio pc como servidor... XD la velocidad no influye en nada, ya que a medida que la vas haciendo la vas testeando en tu pc, gracias a Apache, y al ser un host local, puedes trabajar con ella hasta sin conexión. Al ser php un lenguaje script no necesita compilación, por lo que facilita mucho su programación.
3. Como la cuelgo? He de usar el Cuteftp como una web normal? -> Debes subir los archivos que compongan la web a un servidor que acepte php, si ee servidor no acepta php, la web, logicamente no se verá.
4. Como hago el formato de la web? -> Debes guardarlas con extensión .php en lugar de .html, independientemente de si contiene codigo php o no, el servidor lo ejecutará como una página normal.
Espero haber resuelto tus dudas, si necesitas saber algo más, ya sabes