Shortest representation of an Underload number

Python 2.7 - 87 84 92

u=lambda n:n>1and min([u(i)+u(n/i)for i in range(2,n)if n%i<1]+[':'+u(n-1)+'*'],key=len)or''

Explanation:
This is a pretty straightforward solution. It recursively tests all possible representations of n as either the product of two numbers or as :(n-1)*, and then finds the minimum length solution. range(2,n) is necessary so that the recursion has bounded depth, and n<2 gives the base case.

Notes:
i and n/i are the two factors of n. The ... and ... or ... replacement for ... if ... else ... doesn't work because '' evaluates to false. min of strings gives one of the shortest strings. Python 2.7 saves 1 character by using / instead of //.

Edit: Moved the base case to the back of the expression, allowing me to use ... and ... or ... and shave a couple spaces.

Test cases:

u(1)
''
u(5)
'::*:**'
u(49)
'::*:*:*:*::***'

GolfScript (61 60 55 54 53 chars)

~:X'']({:A{.'.+'\*A{2$+}%~}%}*{,}${1\~X=}?{44/'*:'=}%

This is less tricky than my earlier version and takes a slightly different approach, but it's still brute force. We know that ':'X*'*'X*+ is a candidate solution, so if we generate all well-balanced strings up to that length and take the shortest one which evaluates to the right thing we can be certain to find one.

# Evaluate input and store the target number in X
~:X
# Seed the generator with the empty string
'']
# X times...
({
    # Store the array of strings so far into A
    :A
    # Generate A' by mapping each element
    {
        # Dup: this leaves an untouched copy of the current string
        .
        # Wrap the duplicate in .+
        '.+'\*
        # For each element in A, generate that element suffixed with the current string
        A{2$+}%~
    }%
}*
# Order by length
{,}$
# Find the first element which evaluates to X
{1\~X=}?
# tr .+ :*
{44/'*:'=}%

Thanks to Howard, from whose solution I've stolen a couple of 1-char tweaks.

GolfScript (54 53 chars)

This is an approach which is in the spirit of Howard's (build strings which evaluate to the correct value and select the shortest, rather than brute force through candidate strings to find those which evaluate to the correct value), but is sufficiently different that I think it belongs in a separate answer.

~.''':*':s@,{):x,2>{:^~$x^/~$+{s\*}x^%*}%{,}$0=}/]((=

Online demo not available because it runs a buggy version of the interpreter.

# Let <N> denote the string which evaluates to N
# We want to enter the main loop with three values on the stack: <0> <1> <2>
# However, we'll never use <0>, so we can actually replace that with any value at all.
# Getting the input from underneath 3 items would normally use two stack manipulations.
# Trick: let's use the input value for <0>! (This gives a further bonus later).
# NB We store the value of <2> in the variable s
~.''':*':s@
# for x=1 to input_value ...
,{):x
    # for ^=2 to x-1 ...
    ,2>{:^
        # Use negative stack offsets to index the stack from the start
        # I.e. -1$ gets the first item on the stack, which is <0>
        # -2$ gets the second item on the stack, which is <1>
        # In general, val~$ gets <val>
        ~$x^/~$+
        # We have the string <^><x / ^> on the stack.
        # Increment it (x % ^) times to get a candidate <x>.
        {s\*}x^%*
    }%
    # Select a shortest string.
    {,}$0=
}/
# Group the stack into one array and select the appropriate offset,
# reusing that hacky <0> substitute for the offset.
]((=