First go here and get the datasheet for the microcontroller. Read the table of contents. It has pretty much all information you need. If you take a look at the oscillator section (14.2), you'll see wha you can use with this microcontroller. Basically (if we assume that the watch crystal is 32.768 kHz, but more on that later) you'll need to use capacitors in the 15 pF to 30 pF range for the oscillator to work and use the LP mode. Also from the same page:
Note: Higher capacitance increases the stability of the oscillator,
but also increases the start-up time. These values are for design
guidance only. A series resistor (RS) may be required in HS mode, as
well as XT mode, to avoid overdriving crystals with low drive level
specification. Since each crystal has its own characteristics, the
user should consult the crystal manufac- turer for appropriate values
of external components.
This brings me to my next topic. I'd recommend against using the salvaged crystal if at all possible. While the crystal may be operational, you don't have its specifications and the standard can isn't going to be easy to identify (and the assumption that the crystal is 32.768 kHz may even be wrong!). Instead I'd recommend that you get a crystal from a reputable source and to read the crystal's datasheet. It will probably have more information on the needed capacitors, crystal's accuracy and so on.
Also depending on the amount of work that the microcontroller needs to do, you may end up needing a faster clock, since PICs are a bit slow. For example each instruction needs around four cycles to complete. That gives you around 8192 assembly instructions which you need to execute before updating seconds counter. It may seem like a large number, but it can quickly be eaten up if you're going to do some more complicated programming in C. Be sure to check exactly what compiler gives you and to confirm that the execution time will be good enough. If you only want a clock, then I think that 32.768 kHz would be enough.
The battery side of the equation is also not very simple. You're going to need to precisely adjust the amount of light LEDs provide and compare that to battery capacity, since I expect LEDs to be the major consumers here. Next important point is the mass and the volume of the clock. In general, for easy work with LEDs, you'll want at least some 3 V. That gives us say two AA cells in series. Depending exactly on the circuit you build, you could go up to as much as 4 AA cells in series (but keep in mind that the maximum voltage is 6.5 V for the PIC). If your LED driving circuit is good enough, you may be able to get visible output until the batteries are completely discharged. For more capacity and if space isn't a problem, you could go for even bigger batteries such as C or D cells.
Another option would be to go with higher voltage, but that will bring voltage regulation into equation. You could connect LEDs from same segment in series and use same current for several LEDs and save a bit that way, but on the other hand you'll be wasting power on the regulation for the PIC. If you can get a high efficiency switch mode regulator to provide the needed voltage for the PIC, it would be great (and expensive or complicated), but a linear regulator could be using a bit too much power.
Basically the most important part about voltage is how you drive the LEDs and how good the look at various current levels. You may need to tweak that to get best appearance with minimal current because that will give you greatest reduction in power consumption. Next you could have fund with various sleep states of the microcontroller to make sure its power consumption is low enough. In the end, you'll most likely have to actually measure the current consumption and see check that against the battery datasheets (which are available on web sites of battery manufacturers).
About the comments...
First: I heard that If you connect the LEDs in series you don't get as much light.
Well, yes and no.
When you're making a classical LED circuit consisting of a voltage source, resistor and an LED, you should set the resistor so that the it limits the current going through the LED to a value that will correspond to light level you want. Often this will be the maximum current the LED is rated to use if you want lots of light. The simplified equation would look like this: \$ I_{dmax}=\dfrac {V_{cc}-V_{fd}}{R}\$
If you add another LED to that circuit, each of the LEDs will be less bright than the single LED was because you'll have two forward voltage drops which will decrease the total current through the circuit, so you'll have basically \$I= \dfrac {V_{cc} - 2 V_{fd}}{R} \$ (assuming that this even works in the first place). However to solve that problem you should design the circuit so that the current will be equal to \$I_{dmax}\$ even with two forward voltage drops. In this case, each of the LEDs will be as bright as the LED in the single LED was. That is usually obtained by using a resistor with lower resistance value. Do note that as a group, the two LEDs will emit more light than a single LED.
The main advantage here is that LEDs have large forward voltage drop which is somewhere between 2 and 3 V, depending on the type. You can very easily power several LEDs using a single "high" voltage battery (say 9 V) and share the current among them giving you power savings compared to the case of having each LED connected individually to the voltage source and is better than having LEDs in parallel, since this will produce more light.
Next about the case of several LEDs connected to a single resistor. Well I already asked about it here. The answers seem pretty good to me and explain the problems faced by that setup. Basically, a little bit exaggerated version of what you get is this. If you're fine with that, the circuit is (more or less) OK. If you want to get the maximum out of every LED there, then you need a different setup (and I'm assuming here that each individual LED can take those 14.75 mA). Then there's also this question too.
If you want to reduce the number of resistors, you'll be doing that by decreasing brightness, as I've mentioned. Yes, that can simplify wiring, but you're basically limiting each "segment" to lower brightness than needed. Instead of that (if the available LEDs are too bright), it would be a better idea to get LEDs which are rated for lower current consumption (you can get some which are as low as 2 mA) and save power by using them, since you're on battery.
Also is there any special reason to avoid extra resistors? They won't make a major impact on the total price of the project and if there are any special consideration not mentioned in the original question, please write them so we can provide a better answer.
