I know this questions has really been asked before, though I stil ran into troubles even though had a lot of materials read. My problem is that I can't really handle search and pagination at the same time, because they work perfectly on their own. This part of the script is where the main logic is:
// Quantity of results per page
$limit = 5;
// Check if page has been clicked
if (!isset($_GET['page'])) {
    $page = 1;
} else{
    $page = $_GET['page'];
}
// Initial offset, if page number wasn't specified than start from the very beginning
$starting_limit = ($page-1)*$limit;
// Check if search form has been submitted
if (isset($_GET['search'])) {
    $searchTerm = $_GET['search'];
    $sql = "SELECT company.id, company.name, inn, ceo, city, phone
              FROM company
              LEFT JOIN address ON company.id = address.company_id
              LEFT JOIN contact ON company.id = contact.company_id
              WHERE
                MATCH (company.name, inn, ceo) AGAINST (:searchTerm)
                OR MATCH (city, street) AGAINST (:searchTerm)
                OR MATCH(contact.name, phone, email) AGAINST (:searchTerm)
                ORDER BY id DESC LIMIT $starting_limit, $limit";
    $stmt = $pdo->prepare($sql);
    $stmt->execute(array(':searchTerm' => $searchTerm));
    // Count number of rows to make proper number of pages
    $total_results = $stmt->rowCount();
    $total_pages = ceil($total_results/$limit);
} else { // Basically else clause is similar to the search block except no search is being made
    $sql = "SELECT * FROM company";
    $stmt = $pdo->prepare($sql);
    $stmt->execute();
    // Again count number of rows
    $total_results = $stmt->rowCount();
    $total_pages = ceil($total_results/$limit);
    // And then make a query
    $stmt = $pdo->prepare("
      SELECT company.id, company.name, company.inn,
            company.ceo, address.city, contact.phone
          FROM company
          LEFT JOIN address
          ON company.id = address.company_id
          LEFT JOIN contact
          ON company.id = contact.company_id
          ORDER BY id ASC LIMIT $starting_limit, $limit");
    $stmt->execute();
}
?>
This is pretty much self-explanatory (filling table with returned data):
<?php
       // Filling the result table with results
       while ($row = $stmt->fetch(PDO::FETCH_ASSOC)) {
           echo "<tr><td scope='row'>" . $row['inn'] . "</td>";
           echo "<td><a href='company.php?id=" . $row["id"] . "'>" . $row['name'] . "</a>" . "</td>";
           echo "<td>" . $row['ceo'] . "</td>";
           echo "<td>" . $row['city'] . "</td>";
           echo "<td>" . $row['phone'] . "</td></tr>";
       }
       ?>
And here is the pagination panel:
<?php
    // Debug information - test how many results and pages there actually were
    echo $total_results."\n";
    echo $total_pages;
    // Paginating part itself
    for ($page=1; $page <= $total_pages ; $page++):?>
    <a href='<?php
        if (isset($searchTerm)) {
            echo "pagination_test.php?search=$searchTerm&page=$page";
        } else {
            echo "pagination_test.php?page=$page";
        } ?>' class="links"><?php  echo $page; ?>
    </a>
    <?php endfor; ?>
The problem here is that while pagination itself works perfectly as well as search, but when I combine search and page parameter, I get back only 5 records for any search query ever and the pagination only have 1 page, but I'm still able to go to a page manually and the resulsts are there and correct!
Please, help me figure out what the problem is. Not only that, I started to notice that code become quite sloppy and unmaintanable, I welcome any critique and code organisation/architecture advice on that cause I know something is wrong with this one :)