Need for recursive lookup, stuck in query design
Data model

First of all: fold duplicate entries. I don't see why you would allow reverse duplicates to begin with, so your setup becomes:

CREATE TEMP TABLE tbl(
     pk serial PRIMARY KEY
   , userid int NOT NULL
   , partneruserid int NOT NULL
   , ct int DEFAULT 1 NOT NULL  -- this part is unclear
   , CONSTRAINT user_partner_uni UNIQUE (userid, partneruserid)
   , CONSTRAINT userid_smaller   CHECK  (userid &lt; partneruserid)
   );

INSERT INTO tbl
VALUES 
  (1,1,2,1)
, (2,1,3,2)  -- folded
, (3,1,6,1)
, (4,2,5,1)
, (5,2,6,2)  -- folded
, (7,1,4,1)
, (8,3,5,1)
, (10,3,6,1);


Recursive query

Building on the sanitized model (the constraint userid_smaller is not required for this query, though). This recursive query does basically everything you need:

WITH RECURSIVE  ids (a, z) AS (SELECT 1, 3)  -- enter values here
, cte AS (
   SELECT t.pk, CASE i.a WHEN t.userid THEN t.partneruserid ELSE t.userid END = i.z AS found
        , ARRAY[CASE i.a WHEN t.userid THEN t.partneruserid ELSE t.userid END, i.a] AS path
   FROM   tbl t, ids i
   WHERE  i.a IN (userid, partneruserid)   -- constraint user_id_smaller simplifies this task

   UNION ALL
   SELECT t.pk
        , CASE c.path[1] WHEN t.userid THEN t.partneruserid ELSE t.userid END = i.z AS found
        , CASE c.path[1] WHEN t.userid THEN t.partneruserid ELSE t.userid END || c.path
   FROM   cte c, tbl t, ids i
   WHERE  c.path[1] IN (t.userid, t.partneruserid)
   AND    CASE c.path[1] WHEN t.userid THEN t.partneruserid ELSE t.userid END &lt;&gt; ALL (c.path)
   AND    NOT c.found
   AND    array_length(path,1) &lt; 4
   )
SELECT path, array_length(path,1) - 1 AS steps
FROM   cte c
WHERE  found;


SQL Fiddle

Except for the count. It's unclear how you count duplicate connections exactly. Strictly speaking, you should multiply ct with every step ...

Explanation

The adapted table forces userid to be the lower ID, so the initial predicate can be simplified: userid matches lower ID, partneruserid matches higher ID. If your input is parameterized, you can sort with LEAST (x,y) and GREATEST(x,y) Update: That shortcut only works for short-circuiting in a single step. We need to consider both IDs as starting point for longer paths. Query fixed.

I pick the lower input value (a) as start (could be the other way round) and walk the graph of partnerships until I reach the higher input value (z). Each step can connect to userid or partneruserid, which necessitates the CASE expressions: the match could be on either column, we need to continue with the other column respectively.

We have to remember the path so far (path) and rule out repetitions so not to walk in circles (... &lt;&gt; ALL (c.path)).

I save the last node of the path as first element (path[1]), just to avoid another column for that information. Either way may be more convenient / faster ...

Stop traversing the graph when z is reached (found) or when a given maximum length for the path has been exhausted (array_length(path,1) &lt; 4).

Only rows where z is reached (WHERE  found) are in the final result set. I only collect the bare minimum of information along the way. You can add more columns to the query or / and  JOIN to the original table in the outer query to return more fields.