As far as batteries are concerned, the physics is pretty simple. For a given chemistry, larger volume means more energy available. You can use larger cells, or more cells, or both, to get more energy. Energy is measured in watt-hours (or Joules) and is power multiplied by time. So with more energy, you can run the LEDs at a higher power (i.e. higher brightness), or for a longer time, or a bit of both.
Rechargeable batteries are just like normal batteries but their energy can be replaced when it's been depleted. A power supply provides power continuously; there is no energy limit.
Steve has explained how you can mix LED colours within each string. You can do this in any manner you want. Probably I would connect them in a way that simplifies the connections between them, once you have decided how they will be laid out. If this allows you to repeat a pattern several times, that's a good idea, as Steve mentioned, because if all the strings have the same total LED voltage drop, you only calculate the current limiting resistor value once.
Actually there might be a reason for keeping LEDs of the same colour in the same string - you may want to run the different colours at different currents. For example, red LEDs tend to look brighter than blue LEDs at the same current. So you might want to run all the red LEDs at a lower current than the blue LEDs, or something like that. LEDs that are in the same string operate at the same current, by definition, so you might need to separate them for that reason. Also, you might want certain areas of your sign, or some colours in your sign, to actually appear dimmer or brighter than the others. The same applies in that case too.
A lot of this depends on the type of LEDs you get, how you arrange them, and your personal taste. Also, if you use some kind of plastic front piece to improve contrast, it might affect how the LEDs look as well. Only experimentation will tell you.
If you use a power supply with a regulated output voltage, such as a laptop adapter, you can use resistors for current limiting and the LED brightness will stay the same at all times. If you use batteries (rechargeable or not), you should use a constant current circuit like the one below, instead of resistors, otherwise the LED brightness will drop as the battery discharges.
Here is a diagram for a constant current circuit that can drive multiple LED strings, for use with battery power. It also has adjustable brightness.
The left hand section produces an adjustable voltage on Q2's emitter, which controls the current sink circuits on the right side. In its current form, the circuit can deal with up to about ten LED strings, running at up to 30 mA each.
Current through RD causes a roughly constant voltage drop across the four 1N914 diodes; nominally about 0.7V per diode, so about 2.8V at the top. VR1 and VR2 form a voltage divider that limits the range of voltage at the wiper of VR1 to approximately 2.0 (minimum brightness setting) to 2.8V (maximum brightness setting). VR2 provides exact adjustment of the bottom end of this voltage range.
This voltage is buffered by Q1 and Q2 which are wired as a Darlington transistor. The emitter of Q2 will be about 1.3V lower than the voltage from VR1, i.e. a range of about 0.7V (minimum brightness) to 1.5V (maximum brightness). This voltage is fed to the bases of the current sink transistors.
Each current sink transistor (these are all marked QS) operates independently but is controlled by the voltage from Q2 emitter. The transistor operates as an emitter follower (Wikipedia it), and tries to keep its emitter voltage equal to its base voltage minus about 0.7V. It does this by drawing current through its collector circuit, and therefore through the LEDs.
Since QS's emitter voltage is set to a value between about 0V and 0.8V (depending on the brightness setting), the voltage across the emitter resistor, RE, is a set voltage in the range 0~0.8V (approx), and this causes a controlled (or regulated) current to flow in the collector, depending to the resistance of RE (which is fixed) and the brightness setting, according to Ohm's Law, which is I=V/R.
Ohm's Law says that for a resistor, current = voltage divided by resistance. At maximum brightness setting, voltage is 0.8V. Choosing a resistance of about 40 ohms means that the current will be about 20 mA through the LED string in the collector circuit. When the brightness control is at half way, QS's emitter voltage will be 0.4V and this will produce a collector current of 10 mA. (From Ohm's Law; R=40, V=0.4, I=0.01 amps, or 10 mA.)
An approximate value for RE can be chosen using a rearrangement of Ohm's Law to R = V / I but V=0.8V is only an approximation and it may be better to use a 50 ohm or 100 ohm trimpot for each RE, especially if you want different currents in different strings. Dissipation in RE is not significant at LED string current of 30 mA or less, so any small trimpot will be suitable.
The actual voltage of the battery supply, Vbat, and the voltage dropped by the LED string, Vstring, are not critical, except that (Vbat - Vstring) must be at least 1.2V or so for proper operation of the current sink.
The transistors used for QS may need to be rated for significant power dissipation and/or heatsinked. The power dissipated in each QS transistor is the product of the current through it (in amps) and the voltage across it. This comes from the Power Law, P = V I.
For these calculations, the collector current can be assumed to be the LED current at the maximum brightness setting, and the voltage across the transistor is equal to (Vbat - Vstring - 0.8). The final 0.8 is the voltage across RE at maximum brightness.
Multiplying these numbers gives the power dissipated in the transistor. A small transistor in a TO-92 package (Wikipedia it) has a thermal resistance to ambient of about 100 degrees Celsius per watt. Therefore, if it is dissipating 0.5W and has no heatsink, its temperature will be 50 degrees Celsius above ambient, which feels pretty hot (you can't touch it for very long).
Some suitable transistors for QS, with their maximum collector current and maximum power dissipation figures in parentheses, are:
TO-92:
BC547B (0.1A 0.1W)
BC337 (0.8A 0.6W)
BC635/7/9 (1A 1W)
2N3904 (0.2A 0.6W)
2N4401 (0.6A 0.6W)
SS8050 (1.5A 1W)
Metal can:
2N2222 (0.6A 0.5W)
2N2219 (1A 0.8W)
TO-126:
BD135/7/9 (1.5A 1.2W).
This circuit has a few weaknesses:
1. Current regulation is not well controlled, and LED brightness may vary with ambient temperature and with heating of the transistors in the circuit.
2. Supporting a wide battery voltage range, a wide LED current range, and a widely variable number of LED strings, leads to inefficiency and problems in worst case scenarios. Significant circuit changes would be needed to support a wider variety of applications. For example, QS transistors could be replaced with Darlington transistors (add a fifth 1N914) for high LED string currents and/or a large number of strings.
3. The circuit relies on the sufficient current being available at the collector of each current sink transistor. If the battery voltage drops so low that the voltage at the collector of any QS transistor goes below about 1.2V, which will also happen if any LED chain fails open circuit, Q2 will try to provide a high current, and will overheat rapidly.
I'm thinking about ways to avoid these problems without adding too much complexity. I may post an updated design.
If this circuit is not useful to you, don't feel bad. Driving multiple LED strings with constant current is a common question and I will be able to point other users to this thread.