256 MB est très probablement trop peu. Minecraft démarrera correctement, mais une fois que le monde deviendra suffisamment grand, que ce soit par l'exploration ou la construction de nombreux bâtiments (ce que vos fils ont probablement réussi à réaliser en une heure), 256 MB ne seront pas suffisants et la machine commencera à faire du swapping, c'est-à-dire re/stocker des parties de la RAM sur le disque, ce qui prend du temps et est inutile puisqu'une seule application nécessite toute la RAM. D'expérience, je dirais que 512 MB est le minimum absolu pour des performances acceptables pour deux joueurs qui ne s'éloignent pas trop. Mais comme le suggère cette autre question, même 768 MB entièrement dédiés à une instance autonome basique de Minecraft (un serveur n'a pas besoin de toute la RAM qu'une instance autonome de Minecraft (=client+serveur) nécessite, mais probablement pas beaucoup moins non plus ; et rappelez-vous, il y a un OS qui fonctionne en plus, et même une petite distribution Linux utilisera quand même une partie de la RAM) sont insuffisants.
Donc, non, 256 Mo ne suffiront certainement pas. 1 Go devrait être suffisant pour de petits projets localisés, mais une fois que vous voulez permettre aux joueurs de se disperser dans le monde, même 2 Go peuvent ne pas être suffisants. Bien sûr, pour des communautés plus importantes, vous devriez envisager d'utiliser par exemple bukkit avec un plugin de permissions permettant que seule certaines zones dédiées du monde puissent être modifiées (permanemment), permettant au serveur d'économiser beaucoup de RAM.
À propos, une alternative intéressante à l'utilisation d'un hébergeur est de construire un serveur dédié, par exemple sur un Raspberry Pi à environ 50 $, qui peut apparemment gérer une dizaine de personnes avec des performances acceptables. edit Et peut-être que http://pi.minecraft.net/ améliorera encore davantage cela...