If the device is an off-the-shelf product, and you have no way of knowing what's inside, connecting extra cells in parallel is an option that's safe on the circuitry inside the box, as it will keep the voltage range of the battery the same. For 2x battery life, wire 2 in parallel, for 3x battery life, 3 in parallel. Not 3p2s or 2p3s etc. as adding any in serial will increase the battery pack voltage, which the device's circuitry may not be able to handle.
However you should note that connecting cells in parallel is not without danger to the battery itself. If the cells are not well matched, like if they are different capacity (size), age, state of charge, temperature, and so on, you can get a large current going from one cell to the other when you first connect them, until they equalize in voltage. This current can be high enough to do permanent damage to the cells.
Additionally there is the problem of slightly mismatched capacities, where at the end of a discharge cycle one of the cells will be empty before the other one, so the one with a little energy remaining will provide all the current. The same thing happens at the end of charging, where one gets full earlier and the other is being charged at twice the nominal rate. Unless you take the trouble to put a current meter on each cell, it's an invisible problem, but over many charge/discharge cycles it can do serious damage to the overworked cell, potentially even fire or explosion. When Sanyo recalled some lithium-ion batteries from Lenovo, it was the 3s3p extended packs that were the problem, the same cells in 3s2p were ok. The more cells in parallel, the worse the imbalance problem gets, which is why you generally don't see >3p in commercial products. The battery probably won't catch fire the first time you use it, but statistically over lots of shipped product there can be a higher failure rate. For a hobby project, you can mitigate this by using new cells (not salvage from different old laptop packs) and adding a resistor between the parallel cells as a current limiter at least until they equalize.
All of the above only applies to lithium-ion. If you're using NiMH or NiCd, you probably don't want to connect them in parallel at all. Lithium-ion is easy to charge because you just connect it to a power supply that is both current- and voltage-limited, and turn off the charger when the current falls below some threshold or you get past a timeout (or a safety flag such as temperature). NiCd/NiMH is a lot messier to charge (quickly), you need a circuit that can watch the voltage profile, temperature, etc. (unless you're trickle charging). The imbalance problem would be more difficult. It's probably been done, but when laptops ran from NiCd the packs had a higher voltage because the cells were all in series. Disposable alkalines are always in series because you can expect the user to pick any old cells from the drawer without regard for state of charge. They can already leak if overdischarged, connecting them in parallel would only make the problem worse. Imagine someone mixing NiMH and alkaline AA of various capacity and fullness randomly in both series and parallel - the product will soon be ruined. For a hobby project, nobody's going to care if you ruin a few Energizers, but for anything you'll hand to someone else you should be more careful.
There are other ways to improve your battery life besides connecting extra cells in parallel. Probably the easiest way is simply to use larger cells. For alkaline or NiMH/NiCd, switching from AAA to AA will more than double battery life, and for even more capacity you can use C or D cells. For lithium polymer, there are lots of sizes to choose from, including custom if you need it. If you're using disposable AA or AAA cells you can double battery life by switching from alkaline to Energizer lithium. They cost more than double, so they're more expensive in $/Wh, but they also weigh half as much and they still fit inside the device.
The other posters seem to assume the device is a black box, so perhaps it's not worth discussing too deeply what would happen if you had control over the whole design and added extra cells in series rather than parallel. Basically you'd have to redesign the entire power section - from a higher voltage wall adapter, somewhat different battery charger and protection circuit, different input voltage range to any regulators, possibly an entire redesign to anything powered directly from the battery rather than a regulator.