Use global variables in a class

The correct way to solve this would be to inject the database object into the other class (dependency injection):

$db = new DB_MySQL("localhost", "root", "", "test"); // connect to the database
include_once("pagi.php");

$pagination = new Paginator($db);
$records = $pagination->get_records("SELECT the, fields, you, want, to retrieve FROM `table`");

class Paginator
{    
    protected $db;

    // Might be better to use some generic db interface as typehint when available
    public function __construct(DB_MySQL $db)
    {
        $this->db = $db;
    }

    public function get_records($q) {
        $x = $this->db->query($q);
        return $this->db->fetch($x);
    }

}

Another way you could solve it is by injecting the instance of the database class into the method that uses it:

$db = new DB_MySQL("localhost", "root", "", "test"); // connect to the database
include_once("pagi.php");

$pagination = new Paginator();
$records = $pagination->get_records("SELECT the, fields, you, want, to retrieve FROM `table`", $db);

class Paginator
{
    public function get_records($q, DB_MySQL $db) {
        $x = $db->query($q);
        return $db->fetch($x);
    }

}

Whichever method you choose depends on the situation. If only one method needs an instance of the database you can just inject it into the method, otherwise I would inject it into the constructor of the class.

Also note that I have renamed your class from pagi to Paginator. Paginator is a better name IMHO for the class because it is clear for other people (re)viewing your code. Also note that I have made the first letter uppercase.

Another thing I have done is changed the query to select the fields you are using instead of using the “wildcard” *. This is for the same reason I have changed the classname: People (re)viewing your code will know exactly what fields will be retrieved without checking the database and/or the result.

Update

Because answer gave rise to a discussion regarding why I would go the dependency injection route instead of declaring the object global, I would like to clarify why I would use dependency injection over the global keyword: When you have a method like:

function get_records($q) {
    global $db;

    $x = $db->query($q);
    return $db->fetch($x);
}

When you are using the above method somewhere it isn’t clear that the class or method uses depends on $db. Hence it is a hidden dependency. Another reason why the above is bad is because you have tightly coupled the $db instance (thus the DB_MySQL) class to that method / class. What if you need to use 2 databases at some point. Now you would have to go through all code to change global $db to global $db2. You should never need to change your code just to switch to another database. For this reason, you should not do:

function get_records($q) {
    $db = new DB_MySQL("localhost", "root", "", "test");

    $x = $db->query($q);
    return $db->fetch($x);
}

Again, this is a hidden dependency, and tightly couples the DB_MySQL class to the method / class. Because of this it is also impossible to properly unit test the Paginator class. Instead of testing only the unit (the Paginator class) you are also testing the DB_MySQL class at the same time. And what if you have multiple tightly coupled dependencies? Now you are suddenly testing several classes with your so called unit tests. So when using dependency injection you can easily switch to another database class, or even a mocked one for testing purposes. Besides the benefit of testing only one unit (you don’t have to worry about getting wrong results because of dependencies) it will also make sure your tests will finish fast.

Some people may think the Singleton pattern is the correct way to get access to a database object, but it should be clear, having read all of the above, a singleton is basically just another way of making things global. It might look different, but it has the exact same characteristics and hence the same problems as global.