How to make a linearlayout filling remaining space in a relativelayout?

You should add an id to your second LinearLayout

    <LinearLayout 
        android:orientation="horizontal"
        android:layout_width="fill_parent" 
        android:layout_height="fill_parent"        
        android:layout_below="@+id/category" 
        android:layout_marginTop="10dp"
        android:id="@+id/YOUR_ID">

and in the third layout add android:layout_below="@id/YOUR_ID"

   <LinearLayout 
       android:id="@+id/nav_bar"
       android:layout_below="@id/YOUR_ID"
       android:orientation="horizontal" 
       android:layout_width="fill_parent"        
       android:layout_height="40dp" 
       android:layout_alignParentBottom="true">

You could try using layout weights to control the relative sizes of the child layouts. There is an article on my blog which gives some information on the use of layout weights.

As an example, try this:

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent"
    android:orientation="vertical" >

    <LinearLayout
        android:id="@+id/category"
        android:layout_width="fill_parent"
        android:layout_height="50dp"
        android:orientation="horizontal" >

        <ImageView
            android:id="@+id/back_btn"
            android:layout_width="29dp"
            android:layout_height="34dp"
            android:layout_gravity="center_vertical" />

        <TextView
            android:id="@+id/cat_name"
            android:layout_width="fill_parent"
            android:layout_height="wrap_content"
            android:layout_gravity="center_vertical"
            android:gravity="center"
            android:textSize="20sp" />
    </LinearLayout>

    <LinearLayout
        android:layout_width="fill_parent"
        android:layout_height="fill_parent"
        android:layout_below="@+id/category"
        android:layout_marginTop="10dp"
        android:layout_weight="1"
        android:orientation="horizontal" >

        <ListView
            android:id="@+id/android:list"
            android:layout_width="fill_parent"
            android:layout_height="fill_parent"
            android:background="@android:color/white"
            android:cacheColorHint="@android:color/white" />

        <TextView
            android:id="@+id/android:empty"
            android:layout_width="fill_parent"
            android:layout_height="fill_parent"
            android:background="@android:color/white"
            android:cacheColorHint="@android:color/white"
            android:padding="10dp"
            android:text="no_item" />
    </LinearLayout>

    <LinearLayout
        android:id="@+id/nav_bar"
        android:layout_width="fill_parent"
        android:layout_height="40dp"
        android:orientation="horizontal" >
    //stuff

    </LinearLayout>
</LinearLayout>

The RelativeLayout has been replaced by a LinearLayout, all of the relative positioning tags have been removed, and a layout_weight attribute has been added to the centre LinearLayout which will cause it to stretch to fill the available space.

Nooo... the solution is much simpler! You forgot to say that you wanted the second linear layout to be above the third one :) Yes, the second linear layout must have BOTH android:layout_below="@+id/category" and android:layout_above="@+id/nav_bar". I tested it and it works.

But of course, you can use weights to achieve the same results, it is just going to be harder...

Here is your XML with the change I mentioned (tested it in eclipse):

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="fill_parent"
    android:layout_height="fill_parent" >

    <LinearLayout
        android:id="@+id/category"
        android:layout_width="fill_parent"
        android:layout_height="50dp"
        android:layout_alignParentTop="true"
        android:orientation="horizontal" >

        <ImageView
            android:id="@+id/back_btn"
            android:layout_width="29dp"
            android:layout_height="34dp"
            android:layout_gravity="center_vertical"
            android:src="@drawable/red_arrow_left" />

        <TextView
            android:id="@+id/cat_name"
            android:layout_width="fill_parent"
            android:layout_height="wrap_content"
            android:layout_gravity="center_vertical"
            android:gravity="center"
            android:textSize="20sp" />
    </LinearLayout>

    <LinearLayout
        android:layout_width="fill_parent"
        android:layout_height="fill_parent"
        android:layout_above="@+id/nav_bar"
        android:layout_below="@+id/category"
        android:layout_marginTop="10dp"
        android:orientation="horizontal" >

        <ListView
            android:id="@+id/android:list"
            android:layout_width="fill_parent"
            android:layout_height="fill_parent"
            android:background="@android:color/white"
            android:cacheColorHint="@android:color/white" />

        <TextView
            android:id="@+id/android:empty"
            android:layout_width="fill_parent"
            android:layout_height="fill_parent"
            android:background="@android:color/white"
            android:cacheColorHint="@android:color/white"
            android:padding="10dp"
            android:text="@string/no_item" />
    </LinearLayout>

    <LinearLayout
        xmlns:android="http://schemas.android.com/apk/res/android"
        android:id="@+id/nav_bar"
        android:layout_width="fill_parent"
        android:layout_height="40dp"
        android:layout_alignParentBottom="true"
        android:orientation="horizontal" >
//stuff

    </LinearLayout>
</RelativeLayout>