Magento How to change/define a new layout for category pages(Eg. change from 3 columns to 2 columns)

Changing individual category page layout

This can be done via Magento admin pane.
Go to Catalog->Manage Categories and select the category whose layout you want to change.
Click Custom Design tab on the right.
Select a value for Page Layout from the options.
Save the change by clicking save category and the layout will take effect when you visit the page of this category.

Changing category page layout for all of the pages in your theme's layout/local.xml

Go to the theme folder under the package folder, and open layout/local.xml file or create this file if not exists.
Add the configuration xml below in the file.
<catalog_category_default>
        <reference name="root">
            <action method="setTemplate"><template>page/2columns-right.phtml</template></action>
        </reference>
</catalog_category_default>
Go to System->Configuration and click Design on the left menu.
On the right,choose Themes section and change the Layout input to the theme name you are using.

Changing the page layout for all the pages which include category pages

Open layout/page.xml which might located in /app/design/frontend/base/default/layout/page.xml or your own theme layout folder.
Find the xml configuration below in the xml default node:
<block type="page/html" name="root" output="toHtml" template="page/2columns-left.phtml">.
Here you can change the template to what you want.

Changing multiple category layouts in database which comes from changing individual category page layout in admin pane

Open the table named 'eav_entity_type', and find the entity_type_id where entity_type_code  equal 'catalog_product'. In my example, the entity_type_id is 3.
Open the table named 'eav_attribute' and search the records with the entity_type_id of 3 and find the record whose attribute code is 'page_layout'. And then keep the attribute_id. It is 61 in my database.
Open the table of 'catalog_category_entity_varchar', search by attribute_id of 61. The values of the category layouts will show up. You can change the values and insert new record for categories not in this table as well.