Ellen Sundh has demonstrated in her website how to interface a commercially-available Amplus LED message board with an Arduino. From a hardware perspective it's pretty simple, and Ellen has written her own Arduino library to take care of the software side of the problem. Once again it's great to see people finding ways of controlling items with an Arduino, and tihs is a great example.
Although interfacing with an existing LED display is pretty nifty, an easier way would be to get your hands on one or more of our Freetronics Dot Matrix Display units. Apart from being dead simple to use, they're very bright for indoor and outdoor situations. Available in various colours, the 32 x 16 LED matrix can display text and graphics quite easily - and can be daisy-chained together for extended displays. For more information, see our range of Dot Matrix Displays here.